Integer Programming and Combinatorial Optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007. Proceedings

Kent Andersen, Quentin Louveaux, Robert Weismantel, Laurence A. Wolsey (auth.), Matteo Fischetti, David P. Williamson (eds.)3540727914, 9783540727910

This book constitutes the refereed proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2007, held in Ithaca, NY, USA, in June 2007.

The 36 revised full papers presented were carefully reviewed and selected from over 120 submissions. Among the topics addressed are approximation algorithms, algorithmic game theory, branch and bound algorithms, branch and cut algorithms, computational biology, computational complexity, computational geometry, cutting plane algorithms, diophantine equations, geometry of numbers, graph and network algorithms, integer programming, matroids and submodular functions, on-line algorithms and competitive analysis, polyhedral combinatorics, randomized algorithms, random graphs, scheduling theory and scheduling algorithms, as well as semidefinite programs.

---

Table of contents :
Front Matter….Pages –
Inequalities from Two Rows of a Simplex Tableau….Pages 1-15
Cuts for Conic Mixed-Integer Programming….Pages 16-29
Sequential-Merge Facets for Two-Dimensional Group Problems….Pages 30-42
Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)….Pages 43-52
The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization….Pages 53-67
Finding a Polytope from Its Graph in Polynomial Time….Pages 68-73
Orbitopal Fixing….Pages 74-88
New Variants of Lift-and-Project Cut Generation from the LP Tableau: Open Source Implementation and Testing….Pages 89-103
Orbital Branching….Pages 104-118
Distinct Triangle Areas in a Planar Point Set….Pages 119-129
Scheduling with Precedence Constraints of Low Fractional Dimension….Pages 130-144
Approximation Algorithms for 2-Stage Stochastic Scheduling Problems….Pages 145-157
On Integer Programming and the Branch-Width of the Constraint Matrix….Pages 158-166
Matching Problems in Polymatroids Without Double Circuits….Pages 167-181
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)….Pages 182-196
On a Generalization of the Master Cyclic Group Polyhedron….Pages 197-209
A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applications….Pages 210-224
On the Exact Separation of Mixed Integer Knapsack Cuts….Pages 225-239
A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization….Pages 240-251
On Convex Minimization over Base Polytopes….Pages 252-266
Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems….Pages 267-279
Generating Multiple Solutions for Mixed Integer Programming Problems….Pages 280-294
A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations….Pages 295-309
DINS, a MIP Improvement Heuristic….Pages 310-323
Mixed-Integer Vertex Covers on Bipartite Graphs….Pages 324-336
On the MIR Closure of Polyhedra….Pages 337-351
The Intersection of Continuous Mixing Polyhedra and the Continuous Mixing Polyhedron with Flows….Pages 352-366
Simple Explicit Formula for Counting Lattice Points of Polyhedra….Pages 367-381
Characterizations of Total Dual Integrality….Pages 382-396
Sign-Solvable Linear Complementarity Problems….Pages 397-409
An Integer Programming Approach for Linear Programs with Probabilistic Constraints….Pages 410-423
Infrastructure Leasing Problems….Pages 424-438
Robust Combinatorial Optimization with Exponential Scenarios….Pages 439-453
Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities….Pages 454-468
Optimal Efficiency Guarantees for Network Design Mechanisms….Pages 469-483
The Set Connector Problem in Graphs….Pages 484-498
Back Matter….Pages –