Integer Programming and Combinatorial Optimization: 6th International IPCO Conference Houston, Texas, June 22–24, 1998 Proceedings

Gérard Cornuéjols, Bertrand Guenin, François Margot (auth.), Robert E. Bixby, E. Andrew Boyd, Roger Z. Ríos-Mercado (eds.)9783540645900, 354064590X

This book constitutes the refereeed proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization, IPCO ’98, held in Houston, Texas, USA, in June 1998. The 32 revised papers presented were carefully selected from a total of 77 submissions. The book is divided into sections on O/1 matrices and matroids, edge connectivity, algorithms, integer Programming computation, network flows, scheduling, and quadratic assignment problems.

---

Table of contents :
The Packing Property….Pages 1-8
A Characterization of Weakly Bipartite Graphs….Pages 9-22
Bipartite Designs….Pages 23-36
Characterizing Noninteger Polyhedra with 0–1 Constraints….Pages 37-52
A Theorem of Truemper….Pages 53-68
The Generalized Stable Set Problem for Claw-Free Bidirected Graphs….Pages 69-83
On a Min-max Theorem of Cacti….Pages 84-95
Edge-Splitting and Edge-Connectivity Augmentation in Planar Graphs….Pages 96-111
A New Bound for the 2-Edge Connected Subgraph Problem….Pages 112-125
An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs….Pages 126-136
Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width….Pages 137-152
Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs….Pages 153-168
Approximation Algorithms for the Mixed Postman Problem….Pages 169-179
Improved Approximation Algorithms for Uncapacitated Facility Location….Pages 180-194
The Maximum Traveling Salesman Problem Under Polyhedral Norms….Pages 195-201
Polyhedral Combinatorics of Benzenoid Problems….Pages 202-212
Consecutive Ones and a Betweenness Problem in Computational Biology….Pages 213-228
Solving a Linear Diophantine Equation with Lower and Upper Bounds on the Variables….Pages 229-242
The Intersection of Knapsack Polyhedra and Extensions….Pages 243-256
New Classes of Lower Bounds for Bin Packing Problems….Pages 257-270
Solving Integer and Disjunctive Programs by Lift and Project….Pages 271-283
A Class of Hard Small 0—1 Programs….Pages 284-293
Building Chain and Cactus Representations of All Minimum Cuts from Hao-Orlin in the Same Asymptotic Run Time….Pages 294-309
Simple Generalized Maximum Flow Algorithms….Pages 310-324
The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem….Pages 325-337
An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow….Pages 338-352
Non-approximability Results for Scheduling Problems with Minsum Criteria….Pages 353-366
Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems….Pages 367-382
An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines….Pages 383-393
On the Relationship Between Combinatorial and LP-Based Approaches to NP-Hard Scheduling Problems….Pages 394-408
Polyhedral Combinatorics of Quadratic Assignment Problems with Less Objects than Locations….Pages 409-422
Incorporating Inequality Constraints in the Spectral Bundle Method….Pages 423-435