3. COCOA 2009: Huangshan, China

Ding-Zhu Du, Xiaodong Hu, Panos M. Pardalos (Eds.): Combinatorial Optimization and Applications, Third International Conference, COCOA 2009, Huangshan, China, June 10-12, 2009. Proceedings. Lecture Notes in Computer Science 5573 Springer 2009, ISBN 978-3-642-02025-4

Algorithms for Network Design

Jianping Li, Weidong Li, Jianbo Li:
Polynomial Approximation Schemes for the Max-Min Allocation Problem under a Grade of Service Provision. 1-13
Wei Ding, Guoliang Xue:
A Linear Time Algorithm for Computing the Most Reliable Source on a Tree with Faulty Vertices. 14-23
Tim Nonner, Alexander Souza:
A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines. 24-35
Xianyue Li, Xiao-Hua Xu, Feng Zou, Hongwei Du, Peng-Jun Wan, Yuexuan Wang, Weili Wu:
A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs. 36-48

Suogang Gao, Zengti Li, Jiangchen Yu, Xiaofeng Gao, Weili Wu:
DNA Library Screening, Pooling Design and Unitary Spaces. 49-60
Biing-Feng Wang, Shang-Ju Liu, Chien-Hsin Lin:
Improved Algorithms for the Gene Team Problem. 61-72
Yi Shi, Zhipeng Cai, Guohui Lin, Dale Schuurmans:
Linear Coherent Bi-cluster Discovery via Line Detection and Sample Majority Voting. 73-84

Zhenhua Duan, Chen Yang:
Generalized Russian Cards Problem. 85-97
Anna Beletska, Denis Barthou, Wlodzimierz Bielecki, Albert Cohen:
Computing the Transitive Closure of a Union of Affine Integer Tuple Relations. 98-109
Andreas Karrenbauer:
Matching Techniques Ride to Rescue OLED Displays. 110-122

Huaming Zhang, Milind Vaidya:
On Open Rectangle-of-Influence Drawings of Planar Graphs. 123-134
Jingfa Liu, Yonglei Yao, Yu Zheng, Huantong Geng, Guocheng Zhou:
An Effective Hybrid Algorithm for the Circles and Spheres Packing Problems. 135-144
Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang:
Variable-Size Rectangle Covering. 145-154
Deshi Ye, Xin Han, Guochuan Zhang:
On-Line Multiple-Strip Packing. 155-165

Ruichun Yang, Zhen Wang, Dachuan Xu:
A Cost-Sharing Method for the Soft-Capacitated Economic Lot-Sizing Game. 166-173
Thomas Dueholm Hansen, Orestis Telelis:
Improved Bounds for Facility Location Games with Fair Cost Allocation. 174-185

K. Subramani, Kamesh Madduri:
Two-Level Heaps: A New Priority Queue Structure with Applications to the Single Source Shortest Path Problem. 186-196
He Sun, Hong Zhu:
On Construction of Almost-Ramanujan Graphs. 197-207
Viet Hung Nguyen:
A 2log2(n)-Approximation Algorithm for Directed Tour Cover. 208-218
Ai-fan Ling:
Approximation Algorithms for Max 3-Section Using Complex Semidefinite Programming Relaxation. 219-230

Hai-Zhong Shi, Pan-feng Niu:
Hamiltonian Decomposition of Some Interconnection Networks. 231-237
Jixing Wang:
Infinite Family from Each Vertex k-Critical Graph without Any Critical Edge. 238-248
Baoyindureng Wu, Xinhui An:
A Note on Edge Choosability and Degeneracy of Planar Graphs. 249-257
Hongwei Wang:
A Sufficient and Necessary Condition for the Forcing Number of a Bipartite Graph Being Equal to the Minimum Number of Trailing Vertices. 258-268
Fengwei Li, Qingfang Ye, Baohuai Sheng:
On Integrity of Harary Graphs. 269-278
Yueping Li, Zhe Nie:
A Note on n-Critical Bipartite Graphs and Its Application. 279-286

Xiaoya Li, Jinchuan Cui:
Real-Time Algorithm Scheme for n-Vehicle Exploration Problem. 287-300
Sumit Ganguly:
Deterministically Estimating Data Stream Frequencies. 301-312
Feng Wang, Erika Camacho, Kuai Xu:
Positive Influence Dominating Set in Online Social Networks. 313-321

Yinfeng Xu, Wenming Zhang, Feifeng Zheng:
Optimal Algorithms for the Online Time Series Search Problem. 322-333
Guiqing Zhang, Yinfeng Xu:
A Risk-Reward Competitive Analysis for the Newsboy Problem with Range Information. 334-345
Ming Liu, Yinfeng Xu, Chengbin Chu, Lu Wang:
Optimal Semi-online Algorithm for Scheduling on a Batch Processing Machine. 346-353
Jihuan Ding, Guochuan Zhang:
A Note on Online Scheduling for Jobs with Arbitrary Release Times. 354-362

Zhipeng Cai, Randy Goebel, Guohui Lin:
Size-Constrained Tree Partitioning: A Story on Approximation Algorithm Design for the Multicast k-Tree Routing Problem. 363-374
Eddie Cheng, Shuhong Gao, Ke Qiu, Zhizhang Shen:
On Disjoint Shortest Paths Routing on the Hypercube. 375-383
Hongbing Fan, Yu-Liang Wu:
A New Approach for Rearrangeable Multicast Switching Networks. 384-394

Baoqiang Fan, Rongjun Chen, Guochun Tang:
Bicriteria Scheduling on Single-Machine with Inventory Operations. 395-402
Jianfeng Ren, Yuzhong Zhang, Xianzhao Zhang, Guo Sun:
Approximation Algorithm for Minimizing the Weighted Number of Tardy Jobs on a Batch Machine. 403-410
Yuzhong Zhang, Jianfeng Ren, Chengfei Wang:
Scheduling with Rejection to Minimize the Makespan. 411-420
Rongjun Chen, Baoqiang Fan, Guochun Tang:
Scheduling Problems in Cross Docking. 421-429
Bin Fu, Yumei Huo, Hairong Zhao:
Makespan Minimization with Machine Availability Constraints. 430-437
Zhiyi Tan, An Zhang:
A Mathematical Programming Approach for Online Hierarchical Scheduling. 438-450
Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra, Maria Cristina Pinotti:
Recoverable Robust Timetables on Trees. 451-462
Nasser R. Sabar, Masri Ayob, Graham Kendall, Rong Qu:
Roulette Wheel Graph Colouring for Solving Examination Timetabling Problems. 463-470
Yumei Huo, Joseph Y.-T. Leung, Xin Wang:
Integrated Production and Delivery Scheduling with Disjoint Windows. 471-482

Deying Li, Qinghua Zhu, Huiqiang Yang:
Fault-Tolerant Routing: k-Inconnected Many-to-One Routing in Wireless Networks. 483-493
Xiangyong Li, Yash P. Aneja:
A Branch-and-Cut Algorithm for the Minimum Energy Symmetric Connectivity Problem in Wireless Networks. 494-506
Zheng Li, Deying Li:
Minimum Energy Broadcast Routing in Ad Hoc and Sensor Networks with Directional Antennas. 507-518
Jiguo Yu, Suxia Cui, Guanghui Wang:
Approximating the Multicast Traffic Grooming Problem in Unidirectional SONET/WDM Rings. 519-529
Jiguo Yu, Suxia Cui, Guanghui Wang:
An Algorithm with Better Approximation Ratio for Multicast Traffic in Unidirectional SONET/WDM Rings. 530-540