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

by Cornuejols, Gerard; Burkard, Rainer E.; Woeginger, Gerhard

• ISBN13: 9783540660194
• ISBN10: 3540660194
• Format: Paperback
• Copyright: 1999-06-01
• Publisher: Springer Verlag

Summary

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 Cornuejols-Dawande Instances	1	(16)
K. Aardal
R.E. Bixby
C.A.J. Hurkens
A.K. Lenstra
J.W. Smeltink
Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts	17	(14)
A.A. Ageev
M.I. Sviridenko
Solving the Convex Cost Integer Dual Network Flow Problem	31	(14)
R.K. Ahuja
D.S. Hochbaum
J.B. Orlin
Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem	45	(15)
E. Amaldi
M.E. Pfetsch
L.E. Trotter, Jr.
Valid Inequalities for Problems with Additive Variable Upper Bounds	60	(13)
A. Atamturk
G.L. Nemhauser
M.W.P. Savelsbergh
A Min-Max Theorem on Feedback Vertex Sets	73	(14)
M. Cai
X. Deng
W. Zang
On the Separation of Maximally Violated mod-k Cuts	87	(12)
A. Caprara
M. Fischetti
A.N. Letchford
Improved Approximation Algorithms for Capacitated Facility Location Problems	99	(15)
F.A. Chudak
D.P. Williamson
Optimal 3-Terminal Cuts and Linear Programming	114	(12)
W.H. Cunningham
L. Tang
Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem	126	(11)
D. Cvetkovic
M. Cangalovic
V. Kovacevic-Vujcic
Bounds on the Chvatal Rank of Polytopes in the 0/1-Cube	137	(14)
F. Eisenbrand
A.S. Schulz
Universally Maximum Flow with Piecewise-Constant Capacities	151	(15)
L. Fleischer
Critical Extreme Points of the 2-Edge Connected Spanning Subgraph Polytope	166	(17)
J. Fonlupt
A.R. Mahjoub
An Orientation Theorem with Parity Conditions	183	(8)
A. Frank
T. Jordan
Z. Szigeti
Parity Constrained k-Edge-Connected Orientations	191	(11)
A. Frank
Z. Kiraly
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs	202	(16)
E. Halperin
U. Zwick
On the Chvatal Rank of Certain Inequalities	218	(16)
M. Hartmann
M. Queyranne
Y. Wang
The Square-Free 2-Factor Problem in Bipartite Graphs	234	(8)
D. Hartvigsen
The m-Cost ATSP	242	(17)
C. Helmberg
A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem	259	(14)
S. Iwata
S.T. McCormick
M. Shigeno
Edge-Splitting Problems with Demands	273	(16)
T. Jordan
Integral Polyhedra Associated with Certain Submodular Functions Defined on 012-Vectors	289	(15)
K. Kashiwabara
M. Nakamura
T. Takabatake
Optimal Compaction of Orthogonal Grid Drawings	304	(16)
G.W. Klau
P. Mutzel
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms	320	(8)
P. Klein
N. Young
Experimental Evaluation of Approximation Algorithms for Single-Source Unsplittable Flow	328	(17)
S.G. Kolliopoulos
C. Stein
Approximation Algorithms for a Directed Network Design Problem	345	(16)
V. Melkonian
E. Tardos
Optimizing over All Combinatorial Embeddings of a Planar Graph	361	(16)
P. Mutzel
R. Weiskircher
A Fast Algorithm for Computing Minimum 3-Way and 4-Way Cuts	377	(14)
H. Nagamochi
T. Ibaraki
Scheduling Two Machines with Release Times	391	(9)
J. Noga
S. Seiden
An Introduction to Empty Lattice Simplices	400	(15)
A. Sebo
On Optimal Ear-Decompositions of Graphs	415	(14)
Z. Szigeti
Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications	429	(10)
C.-P. Teo
J. Sethuraman
W.-P. Tan
Vertex-Disjoint Packing of Two Steiner Trees: Polyhedra and Branch-and-Cut	439	(14)
E. Uchoa
M. Poggi de Aragao
Author Index	453