Integer Programming and Combinatorial Optimization: 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005. Proceedings

Matteo Fischetti, Cristiano Saturni (auth.), Michael Jünger, Volker Kaibel (eds.)3540261990, 9783540261995

Since its start in 1990, the IPCO conference series (held under the auspices of theMathematicalProgrammingSociety)hasbecomeanimportantforumforthe presentation of recent results in Integer Programming and Combinatorial Op- mization. This volume compiles the papers presented at IPCO XI, the eleventh conference in this series, held June 8–10, 2005, at the Technische Universit¨ at Berlin. The high interest in this conference series is evident in the large number of submissions. For IPCO XI, 119 extended abstracts of up to 10 pages were submitted. During its meeting on January 29–30, 2005, the Program Committee carefully selected 34 contributions for presentation in non-parallel sessions at the conference. The ?nal choices were not easy at all, since, due to the limited number of time slots, many very good papers could not be accepted. During the selection process the contributions were refereed according to the standards of refereed conferences. As a result of this procedure, you have in your hands a volume that contains papers describing high-quality research e?orts. The page limit for contributions to this proceedings volume was set to 15. You may ?nd full versions of the papers in scienti?c journals in the near future. We thank all the authors who submitted papers. Furthermore, the Program Committee is indebted to the many reviewers who, with their speci?c expertise, helped a lot in making the decisions.

---

Table of contents :
Front Matter….Pages –
Mixed-Integer Cuts from Cyclic Groups….Pages 1-11
Optimizing over the First Chvàtal Closure….Pages 12-22
Sequential Pairing of Mixed Integer Inequalities….Pages 23-34
Approximate Min-max Relations for Odd Cycles in Planar Graphs….Pages 35-50
Disjoint Cycles: Integrality Gap, Hardness, and Approximation….Pages 51-65
A Combinatorial Algorithm to Find a Maximum Even Factor….Pages 66-80
Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems….Pages 81-96
On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem….Pages 97-110
Inventory and Facility Location Models with Market Selection….Pages 111-124
On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations….Pages 125-135
Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials….Pages 136-151
Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut  and Graph Coloring….Pages 152-166
On the Inefficiency of Equilibria in Congestion Games….Pages 167-181
Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times….Pages 182-195
LP-Based Online Scheduling: From Single to Parallel Machines….Pages 196-209
Unique Sink Orientations of Grids….Pages 210-224
Jumping Doesn’t Help in Abstract Cubes….Pages 225-235
Computing the Inertia from Sign Patterns….Pages 236-248
Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem….Pages 249-264
On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem….Pages 265-275
Smoothed Analysis of Integer Programming….Pages 276-290
Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs….Pages 291-305
Approximation Algorithms for Stochastic Inventory Control Models….Pages 306-320
On Two-Stage Stochastic Minimum Spanning Trees….Pages 321-334
Combinatorial Analysis of Generic Matrix Pencils….Pages 335-348
Power Optimization for Connectivity Problems….Pages 349-361
Packing Steiner Forests….Pages 362-376
Bidimensional Packing by Bilinear Programming….Pages 377-391
On the L  ∞  -Norm of Extreme Points for Crossing Supermodular Directed Network LPs….Pages 392-406
Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks….Pages 407-421
Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem….Pages 422-436
Using Grammars to Generate Very Large Scale Neighborhoods for the Traveling Salesman Problem and Other Sequencing Problems….Pages 437-451
A Study of Domino-Parity and k -Parity Constraints for the TSP….Pages 452-467
Not Every GTSP Facet Induces an STSP Facet….Pages 468-482
Back Matter….Pages –