This book constitutes the proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011, held in New York, USA in June 2011.
The 33 papers presented were carefully reviewed and selected from 110 submissions. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization with the aim to present recent developments in theory, computation, and applications. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.
Author(s): Alexander Ageev, Yohann Benchetrit (auth.), Oktay Günlük, Gerhard J. Woeginger (eds.)
Series: Lecture Notes in Computer Science 6655
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2011
Language: English
Pages: 432
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Computer Graphics; Data Structures; Numeric Computing; Computer Communication Networks
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 -
