Integer Programming and Combinatorial Optimization: 4th International IPCO Conference Copenhagen, Denmark, May 29–31, 1995 Proceedings

Alan Frieze, Mark Jerrum (auth.), Egon Balas, Jens Clausen (eds.)3540594086, 9783540594086

This volume constitutes the proceedings of the Fourth International Conference on Integer Programming and Combinatorial Optimization, IPCO ’95, held in Copenhagen in May 1995 under the sponsorship of the Mathematical Programming Society.
Integer programming and combinatorial optimization provide a fruitful theoretical and algorithmic basis for the solution of a number of optimization problems occuring in real-world situations, such as production planning and scheduling, routing, crew scheduling, or network construction. This volume presents 36 revised papers selected from a total of 105 submissions and offers a representative up-to-date snapshot on the state of the art in this interdisciplinary area of research and applications.

---

Table of contents :
Improved approximation algorithms for MAX k -CUT and MAX BISECTION….Pages 1-13
Approximating minimum feedback sets and multi-cuts in directed graphs….Pages 14-28
Nonlinear formulations and improved randomized approximation algorithms for multicut problems….Pages 29-39
Separating clique tree and bipartition inequalities in polynomial time….Pages 40-49
The interval order polytope of a digraph….Pages 50-64
Separation problems for the stable set polytope….Pages 65-79
Computational study of a family of mixed-integer quadratic programming problems….Pages 80-94
A minimal algorithm for the Bounded Knapsack Problem….Pages 95-109
A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems….Pages 110-123
Combining semidefinite and polyhedral relaxations for integer programs….Pages 124-134
Distributed near-optimal matching….Pages 135-144
The random linear bottleneck assignment problem….Pages 145-156
On implementing push-relabel method for the maximum flow problem….Pages 157-171
Use of hidden network structure in the set partitioning problem….Pages 172-184
Generalized max flows and augmenting paths….Pages 185-197
Oriented matroid polytopes and polyhedral fans are signable….Pages 198-211
On combinatorial properties of binary spaces….Pages 212-227
Coverings and delta-coverings….Pages 228-243
The topological structure of maximal lattice free convex bodies: The general case….Pages 244-251
The Hilbert basis of the cut cone over the complete graph K 6 ….Pages 252-266
GRIN: An implementation of Gröbner bases for integer programming….Pages 267-276
Scheduling jobs of equal length: Complexity, facets and computational results….Pages 277-291
Formulating a scheduling problem with almost identical jobs by using positional completion times….Pages 292-306
Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds….Pages 307-320
A mickey-mouse decomposition theorem….Pages 321-328
Minimum cost dynamic flows: The series-parallel case….Pages 329-343
(0, ±1) ideal matrices….Pages 344-359
Embedding graphs in the torus in linear time….Pages 360-363
A characterization of Seymour graphs….Pages 364-372
The Markov chain of colourings….Pages 373-387
Packing algorithms for arborescences (and spanning trees) in capacitated graphs….Pages 388-402
A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem….Pages 403-413
How to make a strongly connected digraph two-connected….Pages 414-425
Polyhedra and optimization in connection with a weak majorization ordering….Pages 426-437
Combining and strengthening Gomory cuts….Pages 438-451
Sequence independent lifting of cover inequalities….Pages 452-461