Ebook: Integer Programming and Combinatorial Optimization: 5th International IPCO Conference Vancouver, British Columbia, Canada, June 3–5, 1996 Proceedings

This volume presents the proceedings of the Fifth Integer Programming and Combinatorial Optimization Conference, IPCO V, held in Vancouver, British Columbia, Canada, in June 1996.
The 36 revised papers included in the book were selected from a total of 99 submissions; they highlight recent developments in theory, computation, and applications of integer programming and combinatorial optimization. The volume is organized in sections on integer programming theory and models, network flow algorithms, approximation algorithms, semi-definite methods, matrix models, set systems and submodularity, scheduling, probabilistic methods, polyhedral methods, and the traveling salesman problem.

---

This volume presents the proceedings of the Fifth Integer Programming and Combinatorial Optimization Conference, IPCO V, held in Vancouver, British Columbia, Canada, in June 1996.
The 36 revised papers included in the book were selected from a total of 99 submissions; they highlight recent developments in theory, computation, and applications of integer programming and combinatorial optimization. The volume is organized in sections on integer programming theory and models, network flow algorithms, approximation algorithms, semi-definite methods, matrix models, set systems and submodularity, scheduling, probabilistic methods, polyhedral methods, and the traveling salesman problem.

---

This volume presents the proceedings of the Fifth Integer Programming and Combinatorial Optimization Conference, IPCO V, held in Vancouver, British Columbia, Canada, in June 1996.
The 36 revised papers included in the book were selected from a total of 99 submissions; they highlight recent developments in theory, computation, and applications of integer programming and combinatorial optimization. The volume is organized in sections on integer programming theory and models, network flow algorithms, approximation algorithms, semi-definite methods, matrix models, set systems and submodularity, scheduling, probabilistic methods, polyhedral methods, and the traveling salesman problem.
Content:
Front Matter....Pages -
Colourful linear programming....Pages 1-15
Test sets and inequalities for integer programs....Pages 16-30
An optimal, stable continued fraction algorithm for arbitrary dimension....Pages 31-43
Algorithms and extended formulations for one and two facility network design....Pages 44-57
Integer multicommodity flow problems....Pages 58-71
A heuristic algorithm for the set covering problem....Pages 72-84
An ?-Relaxation method for generalized separable convex cost network flow problems....Pages 85-93
A network-flow technique for finding low-weight bounded-degree spanning trees....Pages 94-104
Approximating k-set cover and complementary graph coloring....Pages 105-117
On minimum 3-cuts and approximating k-cuts using Cut Trees....Pages 118-131
Primal-dual approximation algorithms for feedback problems in planar graphs....Pages 132-146
Cone-LP's and semidefinite programs: Geometry and a simplex-type method....Pages 147-161
Quadratic knapsack relaxations using cutting planes and semidefinite programming....Pages 162-174
A semidefinite bound for mixing rates of Markov chains....Pages 175-189
The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: Easy and hard cases....Pages 190-203
On optimizing multiplications of sparse matrices....Pages 204-218
Continuous relaxations for Constrained Maximum-Entropy Sampling....Pages 219-233
A submodular optimization problem with side constraints....Pages 234-248
Convexity and Steinitz's exchange property....Pages 249-259
On ideal clutters, metrics and multiflows....Pages 260-274
A supermodular relaxation for scheduling with release dates....Pages 275-287
Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds....Pages 288-300
Implementation of a linear time algorithm for certain generalized traveling salesman problems....Pages 301-315
On dependent randomized rounding algorithms....Pages 316-329
Coloring bipartite hypergraphs....Pages 330-344
Improved randomized approximation algorithms for lot-sizing problems....Pages 345-358
Minimizing total completion time in a two-machine flowshop: Analysis of special cases....Pages 359-373
A new approach to computing optimal schedules for the job-shop scheduling problem....Pages 374-388
Optimal on-line algorithms for single-machine scheduling....Pages 389-403
The strongest facets of the acyclic subgraph polytope are unknown....Pages 404-414
Transitive packing....Pages 415-429
A polyhedral approach to the feedback vertex set problem....Pages 430-444
Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time....Pages 445-459
Separating maximally violated comb inequalities in planar graphs....Pages 460-474
The travelling salesman and the PQ-tree....Pages 475-489
Back Matter....Pages 490-504
....Pages -