Integer Programming and Combinatoral Optimization: 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings

Front Matter....Pages -
An Excluded Minor Characterization of Seymour Graphs....Pages 1-13
Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes....Pages 14-26
A Probabilistic Analysis of the Strength of the Split and Triangle Closures....Pages 27-38
Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation....Pages 39-51
Lift-and-Project Cuts for Mixed Integer Convex Programs....Pages 52-64
TSP on Cubic and Subcubic Graphs....Pages 65-77
Approximability of Capacitated Network Design....Pages 78-91
Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems....Pages 92-103
An Exact Rational Mixed-Integer Programming Solver....Pages 104-116
Valid Inequalities for the Pooling Problem with Binary Variables....Pages 117-129
On the Chvátal-Gomory Closure of a Compact Convex Set....Pages 130-142
Design and Verify: A New Scheme for Generating Cutting-Planes....Pages 143-155
Contact Center Scheduling with Strict Resource Requirements....Pages 156-169
Set Covering with Ordered Replacement: Additive and Multiplicative Gaps....Pages 170-182
Backdoor Branching....Pages 183-191
A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games....Pages 192-206
An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming....Pages 207-222
A New Approach to the Stable Set Problem Based on Ellipsoids....Pages 223-234
Capacitated Vehicle Routing with Non-uniform Speeds....Pages 235-247
Approximation Algorithms for Single and Multi-Commodity Connected Facility Location....Pages 248-260
Safe Lower Bounds for Graph Coloring....Pages 261-273
Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation....Pages 274-286
Constructing Extended Formulations from Reflection Relations....Pages 287-300
Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack....Pages 301-314
Degree Bounded Forest Covering....Pages 315-323
A Primal-Dual Algorithm for Weighted Abstract Cut Packing....Pages 324-335
Convexification Techniques for Linear Complementarity Constraints....Pages 336-348
Iterative Packing for Demand and Hypergraph Matching....Pages 349-361
Universal Packet Routing with Arbitrary Bandwidths and Transit Times....Pages 362-375
A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems....Pages 376-388
Jump Number of Two-Directional Orthogonal Ray Graphs....Pages 389-403
Optimal Matching Forests and Valuated Delta-Matroids....Pages 404-416
Fixed-Charge Transportation on a Path: Linear Programming Formulations....Pages 417-429
Back Matter....Pages -