Integer Programming and Combinatorial Optimization: 7th International IPCO Conference Graz, Austria, June 9–11, 1999 Proceedings

✍ Scribed by Karen Aardal, Robert E. Bixby (auth.), Gérard Cornuéjols, Rainer E. Burkard, Gerhard J. Woeginger (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1999
• Tongue: English
• Leaves: 463
• Series: Lecture Notes in Computer Science 1610
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization, IPCO'99, held in Graz, Austria, in June 1999.
The 33 revised full papers presented were carefully reviewed and selected from a total of 99 submissions. Among the topics addressed are theoretical, computational, and application-oriented aspects of approximation algorithms, branch and bound algorithms, computational biology, computational complexity, computational geometry, cutting plane algorithms, diaphantine equations, geometry of numbers, graph and network algorithms, online algorithms, polyhedral combinatorics, scheduling, and semidefinite programs.

✦ Table of Contents

Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances....Pages 1-16
Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts....Pages 17-30
Solving the Convex Cost Integer Dual Network Flow Problem....Pages 31-44
Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem....Pages 45-59
Valid Inequalities for Problems with Additive Variable Upper Bounds....Pages 60-72
A Min-Max Theorem on Feedback Vertex Sets (Preliminary Version)....Pages 73-86
On the Separation of Maximally Violated mod- k Cuts....Pages 87-98
Improved Approximation Algorithms for Capacitated Facility Location Problems....Pages 99-113
Optimal 3-Terminal Cuts and Linear Programming....Pages 114-125
Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem....Pages 126-136
Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube....Pages 137-150
Universally Maximum Flow with Piecewise-Constant Capacities....Pages 151-165
Critical Extreme Points of the 2-Edge Connected Spannning Subgraph Polytope....Pages 166-182
An Orientation Theorem with Parity Conditions....Pages 183-190
Parity Constrained k -Edge-Connected Orientations....Pages 191-201
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs....Pages 202-217
On the Chvátal Rank of Certain Inequalities....Pages 218-233
The Square-Free 2-Factor Problem in Bipartite Graphs....Pages 234-241
The m-Cost ATSP....Pages 242-258
A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem....Pages 259-272
Edge-Splitting Problems with Demands....Pages 273-288
Integral Polyhedra Associated with Certain Submodular Functions Defined on 012-Vectors....Pages 289-303
Optimal Compaction of Orthogonal Grid Drawings (Extended Abstract)....Pages 304-319
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms....Pages 320-327
Experimental Evaluation of Approximation Algorithms for Single-Source Unsplittable Flow....Pages 328-344
Approximation Algorithms for a Directed Network Design Problem....Pages 345-360
Optimizing over All Combinatorial Embeddings of a Planar Graph (Extended Abstract)....Pages 361-376
A Fast Algorithm for Computing Minimum 3-Way and 4-Way Cuts....Pages 377-390
Scheduling Two Machines with Release Times....Pages 391-399
An Introduction to Empty Lattice Simplices....Pages 400-414
On Optimal Ear-Decompositions of Graphs....Pages 415-428
Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications (Extended Abstract)....Pages 429-438
Vertex-Disjoint Packing of Two Steiner Trees: Polyhedra and Branch-and-Cut....Pages 439-452

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Combinatorics; Calculus of Variations and Optimal Control; Optimization