This book constitutes the refereed proceedings of the Third International Conference on Combinatorial Optimization and Applications, COCOA 2009, held in Huangshan, China, in June 2009.
The 50 revised full papers were carefully reviewed and selected from 103 submissions. The papers feature original research in the areas of combinatorial optimization - both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.
Author(s): Jianping Li, Weidong Li, Jianbo Li (auth.), Ding-Zhu Du, Xiaodong Hu, Panos M. Pardalos (eds.)
Series: Lecture Notes in Computer Science 5573 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 542
Tags: Algorithm Analysis and Problem Complexity; Algorithms; Discrete Mathematics in Computer Science; Software Engineering; Computer Communication Networks; Coding and Information Theory
Front Matter....Pages -
Polynomial Approximation Schemes for the Max-Min Allocation Problem under a Grade of Service Provision....Pages 1-13
A Linear Time Algorithm for Computing the Most Reliable Source on a Tree with Faulty Vertices....Pages 14-23
A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines....Pages 24-35
A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs....Pages 36-48
DNA Library Screening, Pooling Design and Unitary Spaces....Pages 49-60
Improved Algorithms for the Gene Team Problem....Pages 61-72
Linear Coherent Bi-cluster Discovery via Line Detection and Sample Majority Voting....Pages 73-84
Generalized Russian Cards Problem....Pages 85-97
Computing the Transitive Closure of a Union of Affine Integer Tuple Relations....Pages 98-109
Matching Techniques Ride to Rescue OLED Displays....Pages 110-122
On Open Rectangle-of-Influence Drawings of Planar Graphs....Pages 123-134
An Effective Hybrid Algorithm for the Circles and Spheres Packing Problems....Pages 135-144
Variable-Size Rectangle Covering....Pages 145-154
On-Line Multiple-Strip Packing....Pages 155-165
A Cost-Sharing Method for the Soft-Capacitated Economic Lot-Sizing Game....Pages 166-173
Improved Bounds for Facility Location Games with Fair Cost Allocation....Pages 174-185
Two-Level Heaps: A New Priority Queue Structure with Applications to the Single Source Shortest Path Problem....Pages 186-196
On Construction of Almost-Ramanujan Graphs....Pages 197-207
A 2log 2 ( n )-Approximation Algorithm for Directed Tour Cover....Pages 208-218
Approximation Algorithms for Max 3-Section Using Complex Semidefinite Programming Relaxation....Pages 219-230
Hamiltonian Decomposition of Some Interconnection Networks....Pages 231-237
Infinite Family from Each Vertex k -Critical Graph without Any Critical Edge....Pages 238-248
A Note on Edge Choosability and Degeneracy of Planar Graphs....Pages 249-257
A Sufficient and Necessary Condition for the Forcing Number of a Bipartite Graph Being Equal to the Minimum Number of Trailing Vertices....Pages 258-268
On Integrity of Harary Graphs....Pages 269-278
A Note on n -Critical Bipartite Graphs and Its Application....Pages 279-286
Real-Time Algorithm Scheme for n -Vehicle Exploration Problem....Pages 287-300
Deterministically Estimating Data Stream Frequencies....Pages 301-312
Positive Influence Dominating Set in Online Social Networks....Pages 313-321
Optimal Algorithms for the Online Time Series Search Problem....Pages 322-333
A Risk-Reward Competitive Analysis for the Newsboy Problem with Range Information....Pages 334-345
Optimal Semi-online Algorithm for Scheduling on a Batch Processing Machine....Pages 346-353
A Note on Online Scheduling for Jobs with Arbitrary Release Times....Pages 354-362
Size-Constrained Tree Partitioning: A Story on Approximation Algorithm Design for the Multicast k -Tree Routing Problem....Pages 363-374
On Disjoint Shortest Paths Routing on the Hypercube....Pages 375-383
A New Approach for Rearrangeable Multicast Switching Networks....Pages 384-394
Bicriteria Scheduling on Single-Machine with Inventory Operations....Pages 395-402
Approximation Algorithm for Minimizing the Weighted Number of Tardy Jobs on a Batch Machine....Pages 403-410
Scheduling with Rejection to Minimize the Makespan....Pages 411-420
Scheduling Problems in Cross Docking....Pages 421-429
Makespan Minimization with Machine Availability Constraints....Pages 430-437
A Mathematical Programming Approach for Online Hierarchical Scheduling....Pages 438-450
Recoverable Robust Timetables on Trees....Pages 451-462
Roulette Wheel Graph Colouring for Solving Examination Timetabling Problems....Pages 463-470
Integrated Production and Delivery Scheduling with Disjoint Windows....Pages 471-482
Fault-Tolerant Routing: k -Inconnected Many-to-One Routing in Wireless Networks....Pages 483-493
A Branch-and-Cut Algorithm for the Minimum Energy Symmetric Connectivity Problem in Wireless Networks....Pages 494-506
Minimum Energy Broadcast Routing in Ad Hoc and Sensor Networks with Directional Antennas....Pages 507-518
Approximating the Multicast Traffic Grooming Problem in Unidirectional SONET/WDM Rings....Pages 519-529
An Algorithm with Better Approximation Ratio for Multicast Traffic in Unidirectional SONET/WDM Rings....Pages 530-540
Back Matter....Pages -
