Integer Programming and Combinatorial Optimization

1. Front Matter

   Pages I-XI

   PDF

2. Two O(log^* k)-Approximation Algorithms for the Asymmetric k-Center Problem

   • Aaron Archer

   Pages 1-14

3. Strongly Polynomial Algorithms for the Unsplittable Flow Problem

   • Yossi Azar, Oded Regev

   Pages 15-29

4. Edge Covers of Setpairs and the Iterative Rounding Method

   • Joseph Cheriyan, Santosh Vempala

   Pages 30-44

5. The Asymptotic Performance Ratio of an On-Line Algorithm for Uniform Parallel Machine Scheduling with Release Dates

   • Cheng-Feng Mabel Chou, Maurice Queyranne, David Simchi-Levi

   Pages 45-59

6. Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation

   • Fabián A. Chudak, Tim Roughgarden, David P. Williamson

   Pages 60-70

7. On the Rank of Mixed 0,1 Polyhedra

   • Gérard Cornuéjols, Yanjun Li

   Pages 71-77

8. Fast 2-Variable Integer Programming

   • Friedrich Eisenbrand, Günter Rote

   Pages 78-89

9. Approximating k-Spanner Problems for k > 2

   • Michael Elkin, David Peleg

   Pages 90-104

10. A Matroid Generalization of the Stable Matching Polytope

    • Tamás Fleiner

    Pages 105-114

11. A 2-Approximation for Minimum Cost {0, 1, 2} Vertex Connectivity

    • Lisa Fleischer

    Pages 115-129

12. Combined Connectivity Augmentation and Orientation Problems

    • András Frank, Tamás Király

    Pages 130-144

13. An Extension of a Theorem of Henneberg and Laman

    • András Frank, László Szegő

    Pages 145-159

14. Bisubmodular Function Minimization

    • Satoru Fujishige, Satoru Iwata

    Pages 160-169

15. On the Integrality Gap of a Natural Formulation of the Single-sink Buy-at-Bulk Network Design Problem

    • Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. S. Salman, Amitabh Sinha

    Pages 170-184

16. Circuit Mengerian Directed Graphs

    • Bertrand Guenin

    Pages 185-195

17. Integral Polyhedra Related to Even Cycle and Even Cut Matroids

    • Bertrand Guenin

    Pages 196-209

18. A Unified Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems

    • Eran Halperin, Uri Zwick

    Pages 210-225

19. Synthesis of 2-Commodity Flow Networks

    • Refael Hassin, Asaf Levin

    Pages 226-235

20. Bounds for Deterministic Periodic Routing sequences

    • A. Hordijk, D. A. van der Laan

    Pages 236-250

This volume contains the papers selected for presentation at IPCO VIII, the Eighth Conference on Integer Programming and Combinatorial Optimization, Utrecht, The Netherlands, 2001. This meeting isa forum for researchers and practitioners working on various aspects of integer programming and combi- torial optimization. The aim is to present recent developments in theory, com- tation, and application of integer programming and combinatorial optimization. Topics include, but are not limited to: approximation algorithms, branch and bound algorithms, computational biology, computational complexity, compu- tional geometry, cutting plane algorithms, diophantine equations, geometry of numbers, graph and network algorithms, integer programming, matroids and submodular functions, on-line algorithms, polyhedral combinatorics, scheduling theory and algorithms, and semide nit e programs. IPCO was established in 1988 when the rs t IPCO program committee was formed. The locations and years of the seven rs t IPCO conferences were: IPCO I, Waterloo (Canada) 1990, IPCO II, Pittsburgh (USA) 1992, IPCO III, - ice (Italy) 1993, IPCO IV, Copenhagen (Denmark) 1995, IPCO V, Vancouver (Canada) 1996, IPCO VI, Houston (USA) 1998, IPCO VII, Graz (Austria) 1999. IPCO is held every year in which no MPS (Mathematical Programming Society) International Symposium takes place. Since the MPS meeting is triennial, IPCO conferences are held twice in every three-year period. Asa rule, IPCO is held somewhere in Northern America in even years, and somewhere in Europe in odd years.

• Approximation
• Approximation Algorithms
• Computational Complexity
• Discrete Mathematics
• Graph Algorithms
• Integer Programming
• Mathematical Programming
• Network Algorithms
• Scheduling Computational Geometry
• Variable
• algorithms
• combinatorial optimization
• complexity
• optimization
• programming
• algorithm analysis and problem complexity
• combinatorics

• Instituut voor Informatica en Informatiekunde, Universiteit Utrecht, CH Utrecht, The Netherlands

  Karen Aardal

• CWI, SJ Amsterdam, The Netherlands

  Bert Gerards

Policies and ethics