Combinatorial Optimization and Applications: Third International Conference, COCOA 2009, Huangshan, China, June 10-12, 2009. Proceedings

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 -