Imre Bárány, Shmuel Onn (auth.), William H. Cunningham, S. Thomas McCormick, Maurice Queyranne (eds.)3540613102, 9783540613107
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.
Table of contents :
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
Reviews
There are no reviews yet.