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

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