Integer Programming and Combinatorial Optimization: 9th International IPCO Conference Cambridge, MA, USA, May 27–29, 2002 Proceedings

Satoru Iwata (auth.), William J. Cook, Andreas S. Schulz (eds.)9783540436768, 3540436766

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.

---

Table of contents :
A Faster Scaling Algorithm for Minimizing Submodular Functions….Pages 1-8
A Generalization of Edmonds’ Matching and Matroid Intersection Algorithms….Pages 9-20
A Coordinatewise Domain Scaling Algorithm for M-convex Function Minimization….Pages 21-35
The Quickest Multicommodity Flow Problem….Pages 36-53
A New Min-Cut Max-Flow Ratio for Multicommodity Flows….Pages 54-66
Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems….Pages 67-82
Finding the Exact Integrality Gap for Small Traveling Salesman Problems….Pages 83-92
Polynomial-Time Separation of Simple Comb Inequalities….Pages 93-108
A New Approach to Cactus Construction Applied to TSP Support Graphs….Pages 109-126
Split Closure and Intersection Cuts….Pages 127-144
An Exponential Lower Bound on the Length of Some Classes of Branch-and-Cut Proofs….Pages 145-160
Lifted Inequalities for 0-1 Mixed Integer Programming: Basic Theory and Algorithms….Pages 161-175
On a Lemma of Scarf….Pages 176-187
A Short Proof of Seymour’s Characterization of the Matroids with the Max-Flow Min-Cut Property….Pages 188-193
Integer Programming and Arrovian Social Welfare Functions….Pages 194-211
Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design….Pages 212-229
The Minimum Latency Problem Is NP-Hard for Weighted Trees….Pages 230-239
An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem….Pages 240-257
A Polyhedral Approach to Surface Reconstruction from Planar Contours….Pages 258-272
The Semidefinite Relaxation of the k -Partition Polytope Is Strong….Pages 273-290
A Polyhedral Study of the Cardinality Constrained Knapsack Problem….Pages 291-303
A PTAS for Minimizing Total Completion Time of Bounded Batch Scheduling….Pages 304-314
An Approximation Scheme for the Two-Stage, Two-Dimensional Bin Packing Problem….Pages 315-328
On Preemptive Resource Constrained Scheduling: Polynomial-Time Approximation Schemes….Pages 329-349
Hard Equality Constrained Integer Knapsacks….Pages 350-366
The Distribution of Values in the Quadratic Assignment Problem….Pages 367-383
A New Subadditive Approach to Integer Programming….Pages 384-400
Improved Approximation Algorithms for Resource Allocation….Pages 401-414
Approximating the Advertisement Placement Problem….Pages 415-424
Algorithms for Minimizing Response Time in Broadcast Scheduling….Pages 425-438
Building Edge-Failure Resilient Networks….Pages 439-456
The Demand Matching Problem….Pages 457-474
The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap….Pages 475-486