Integer Programming and Combinatorial Optimization

1. Front Matter

   Pages I-XI

   PDF

2. A Faster Scaling Algorithm for Minimizing Submodular Functions

   • Satoru Iwata

   Pages 1-8

3. A Generalization of Edmonds’ Matching and Matroid Intersection Algorithms

   • Bianca Spille, Robert Weismantel

   Pages 9-20

4. A Coordinatewise Domain Scaling Algorithm for M-convex Function Minimization

   • Akihisa Tamura

   Pages 21-35

5. The Quickest Multicommodity Flow Problem

   • Lisa Fleischer, Martin Skutella

   Pages 36-53

6. A New Min-Cut Max-Flow Ratio for Multicommodity Flows

   • Oktay Günlük

   Pages 54-66

7. Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems

   • Michael Lewin, Dror Livnat, Uri Zwick

   Pages 67-82

8. Finding the Exact Integrality Gap for Small Traveling Salesman Problems

   • Sylvia Boyd, Geneviève Labonté

   Pages 83-92

9. Polynomial-Time Separation of Simple Comb Inequalities

   • Adam N. Letchford, Andrea Lodi

   Pages 93-108

10. A New Approach to Cactus Construction Applied to TSP Support Graphs

    • Klaus M. Wenger

    Pages 109-126

11. Split Closure and Intersection Cuts

    • Kent Andersen, Gérard Cornuéjols, Yanjun Li

    Pages 127-144

12. An Exponential Lower Bound on the Length of Some Classes of Branch-and-Cut Proofs

    • Sanjeeb Dash

    Pages 145-160

13. Lifted Inequalities for 0-1 Mixed Integer Programming: Basic Theory and Algorithms

    • Jean-Philippe P. Richard, Ismael R. de Farias Jr, George L. Nemhauser

    Pages 161-175

14. On a Lemma of Scarf

    • Ron Aharoni, Tamás Fleiner

    Pages 176-187

15. A Short Proof of Seymour’s Characterization of the Matroids with the Max-Flow Min-Cut Property

    • Bertrand Guenin

    Pages 188-193

16. Integer Programming and Arrovian Social Welfare Functions

    • Jay Sethuraman, Chung-Piaw Teo, Rakesh V. Vohra

    Pages 194-211

17. Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design

    • Ramamoorthi Ravi, Amitabh Sinha

    Pages 212-229

18. The Minimum Latency Problem Is NP-Hard for Weighted Trees

    • René Sitters

    Pages 230-239

19. An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

    • Maxim Sviridenko

    Pages 240-257

20. A Polyhedral Approach to Surface Reconstruction from Planar Contours

    • Ernst Althaus, Christian Fink

    Pages 258-272

This volume contains the papers selected for presentation at IPCO 2002, the NinthInternationalConferenceonIntegerProgrammingandCombinatorial- timization, Cambridge, MA (USA), May 27–29, 2002. The IPCO series of c- ferences highlights recent developments in theory, computation, and application of integer programming and combinatorial optimization. IPCO was established in 1988 when the ?rst IPCO program committee was formed. IPCO is held every year in which no International Symposium on Ma- ematical Programming (ISMP) takes places. The ISMP is triennial, so IPCO conferences are held twice in every three-year period. The eight previous IPCO conferences were held in Waterloo (Canada) 1990, Pittsburgh (USA) 1992, Erice (Italy) 1993, Copenhagen (Denmark) 1995, Vancouver (Canada) 1996, Houston (USA) 1998, Graz (Austria) 1999, and Utrecht (The Netherlands) 2001. In response to the call for papers for IPCO 2002, the program committee received 110 submissions, a record number for IPCO. The program committee met on January 7 and 8, 2002, in Aussois (France), and selected 33 papers for inclusion in the scienti?c program of IPCO 2002. The selection was based on originality and quality, and re?ects many of the current directions in integer programming and combinatorial optimization research.

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

• Program in Applied and Computational Mathematics, University of Princeton, Princeton, USA

  William J. Cook

• Sloan School of Management, Massachusetts Institute of Technology, Cambridge, USA

  Andreas S. Schulz

Policies and ethics