Combinatorial Optimization and Applications

1. Front Matter

   PDF

2. Algorithms for Network Design

   1. Polynomial Approximation Schemes for the Max-Min Allocation Problem under a Grade of Service Provision

      • Jianping Li, Weidong Li, Jianbo Li

      Pages 1-13

   2. A Linear Time Algorithm for Computing the Most Reliable Source on a Tree with Faulty Vertices

      • Wei Ding, Guoliang Xue

      Pages 14-23

   3. A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines

      • Tim Nonner, Alexander Souza

      Pages 24-35

   4. A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs

      • Xianyue Li, Xiao-Hua Xu, Feng Zou, Hongwei Du, Pengjun Wan, Yuexuan Wang et al.

      Pages 36-48

3. Bioinformatics

   1. DNA Library Screening, Pooling Design and Unitary Spaces

      • Suogang Gao, Zengti Li, Jiangchen Yu, Xiaofeng Gao, Weili Wu

      Pages 49-60

   2. Improved Algorithms for the Gene Team Problem

      • Biing-Feng Wang, Shang-Ju Liu, Chien-Hsin Lin

      Pages 61-72

   3. Linear Coherent Bi-cluster Discovery via Line Detection and Sample Majority Voting

      • Yi Shi, Zhipeng Cai, Guohui Lin, Dale Schuurmans

      Pages 73-84

4. Combinatorics and Its Applications

   1. Generalized Russian Cards Problem

      • Zhenhua Duan, Chen Yang

      Pages 85-97

   2. Computing the Transitive Closure of a Union of Affine Integer Tuple Relations

      • Anna Beletska, Denis Barthou, Wlodzimierz Bielecki, Albert Cohen

      Pages 98-109

   3. Matching Techniques Ride to Rescue OLED Displays

      • Andreas Karrenbauer

      Pages 110-122

5. Computational Geometry

   1. On Open Rectangle-of-Influence Drawings of Planar Graphs

      • Huaming Zhang, Milind Vaidya

      Pages 123-134

   2. An Effective Hybrid Algorithm for the Circles and Spheres Packing Problems

      • Jingfa Liu, Yonglei Yao, Yu Zheng, Huantong Geng, Guocheng Zhou

      Pages 135-144

   3. Variable-Size Rectangle Covering

      • Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang

      Pages 145-154

   4. On-Line Multiple-Strip Packing

      • Deshi Ye, Xin Han, Guochuan Zhang

      Pages 155-165

6. Game Theory

   1. A Cost-Sharing Method for the Soft-Capacitated Economic Lot-Sizing Game

      • Ruichun Yang, Zhen Wang, Dachuan Xu

      Pages 166-173

   2. Improved Bounds for Facility Location Games with Fair Cost Allocation

      • Thomas Dueholm Hansen, Orestis A. Telelis

      Pages 174-185

7. Graph Algorithms

   1. Two-Level Heaps: A New Priority Queue Structure with Applications to the Single Source Shortest Path Problem

      • K. Subramani, Kamesh Madduri

      Pages 186-196

   2. On Construction of Almost-Ramanujan Graphs

      • He Sun, Hong Zhu

      Pages 197-207

   3. A 2log₂(n)-Approximation Algorithm for Directed Tour Cover

      • Viet Hung Nguyen

      Pages 208-218

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.

• algorithms
• bioinformatics
• combinatorial optimization
• combinatorics
• computational geometry
• game theory
• graph algorithms
• graph theory
• network design
• network models
• optical networks
• optimization
• routing
• scheduling
• wireless networks
• algorithm analysis and problem complexity

• Department of Computer Science, University of Texas at Dallas, Richardson, USA

  Ding-Zhu Du

• Chinese Academy of Sciences, Institute of Applied Mathematics, Beijing, P. R. China

  Xiaodong Hu

• Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

  Panos M. Pardalos

Policies and ethics