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

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
Finding real-valued single-source shortest paths in o ( n 3 ) expected time....Pages 94-104
A network-flow technique for finding low-weight bounded-degree spanning trees....Pages 105-117
Approximating k -set cover and complementary graph coloring....Pages 118-131
On minimum 3-cuts and approximating k-cuts using Cut Trees....Pages 132-146
Primal-dual approximation algorithms for feedback problems in planar graphs....Pages 147-161
Cone-LP\'s and semidefinite programs: Geometry and a simplex-type method....Pages 162-174
Quadratic knapsack relaxations using cutting planes and semidefinite programming....Pages 175-189
A semidefinite bound for mixing rates of Markov chains....Pages 190-203
The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: Easy and hard cases....Pages 204-218
On optimizing multiplications of sparse matrices....Pages 219-233
Continuous relaxations for Constrained Maximum-Entropy Sampling....Pages 234-248
A submodular optimization problem with side constraints....Pages 249-259
Convexity and Steinitz\'s exchange property....Pages 260-274
On ideal clutters, metrics and multiflows....Pages 275-287
A supermodular relaxation for scheduling with release dates....Pages 288-300
Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds....Pages 301-315
Implementation of a linear time algorithm for certain generalized traveling salesman problems....Pages 316-329
On dependent randomized rounding algorithms....Pages 330-344
Coloring bipartite hypergraphs....Pages 345-358
Improved randomized approximation algorithms for lot-sizing problems....Pages 359-373
Minimizing total completion time in a two-machine flowshop: Analysis of special cases....Pages 374-388
A new approach to computing optimal schedules for the job-shop scheduling problem....Pages 389-403
Optimal on-line algorithms for single-machine scheduling....Pages 404-414
The strongest facets of the acyclic subgraph polytope are unknown....Pages 415-429
Transitive packing....Pages 430-444
A polyhedral approach to the feedback vertex set problem....Pages 445-459
Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time....Pages 460-474
Separating maximally violated comb inequalities in planar graphs....Pages 475-489
The travelling salesman and the PQ-tree....Pages 490-504