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

Softcover

ISBN 10: 3662171538 ISBN 13: 9783662171530

Publisher: Springer, 2014

Synopsis

Improved approximation algorithms for MAX k-CUT and MAX BISECTION.- Approximating minimum feedback sets and multi-cuts in directed graphs.- Nonlinear formulations and improved randomized approximation algorithms for multicut problems.- Separating clique tree and bipartition inequalities in polynomial time.- The interval order polytope of a digraph.- Separation problems for the stable set polytope.- Computational study of a family of mixed-integer quadratic programming problems.- A minimal algorithm for the Bounded Knapsack Problem.- A framework for tightening 0-1 programs based on extensions of pure 0-1 KP and SS problems.- Combining semidefinite and polyhedral relaxations for integer programs.- Distributed near-optimal matching.- The random linear bottleneck assignment problem.- On implementing push-relabel method for the maximum flow problem.- Use of hidden network structure in the set partitioning problem.- Generalized max flows and augmenting paths.- Oriented matroid polytopes and polyhedral fans are signable.- On combinatorial properties of binary spaces.- Coverings and delta-coverings.- The topological structure of maximal lattice free convex bodies: The general case.- The Hilbert basis of the cut cone over the complete graph K 6.- GRIN: An implementation of Gröbner bases for integer programming.- Scheduling jobs of equal length: Complexity, facets and computational results.- Formulating a scheduling problem with almost identical jobs by using positional completion times.- Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds.- A mickey-mouse decomposition theorem.- Minimum cost dynamic flows: The series-parallel case.- (0, ±1) ideal matrices.- Embedding graphs in the torus in linear time.- A characterization of Seymour graphs.- The Markov chain of colourings.- Packing algorithms for arborescences (and spanning trees) in capacitated graphs.- A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem.- How to make a strongly connected digraph two-connected.- Polyhedra and optimization in connection with a weak majorization ordering.- Combining and strengthening Gomory cuts.- Sequence independent lifting of cover inequalities.

Edition details

• Publisher: Springer
• Publication date: 2014
• ISBN 10: 3662171538
• ISBN 13: 9783662171530
• Binding: Paperback
• Language: English
• Number of pages: 484
• Editor: Balas Egon, Clausen Jens