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

Front Cover
Springer Science & Business Media, May 19, 1999 - Computers - 452 pages
This volume contains the papers selected for presentation at IPCO VII, the Seventh Conference on Integer Programming and Combinatorial Optimization, Graz, Austria, June9{11,1999.Thismeetingisaforumforresearchersandpr- titioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, compu- tion, and applications of integer programming and combinatorial optimization. Topics include, but are not limited to: approximation algorithms, branch and bound algorithms, computational biology, computational complexity, compu- tional geometry, cutting plane algorithms, diophantine equations, geometry of numbers, graph and network algorithms, integer programming, matroids and submodular functions, on-line algorithms, polyhedral combinatorics, scheduling theory and algorithms, and semide nite programs. IPCO was established in 1988 when the rst IPCO program committee was formed. IPCO I took place in Waterloo (Canada) in 1990, IPCO II was held in Pittsburgh (USA) in 1992, IPCO III in Erice (Italy) 1993, IPCO IV in Cop- hagen (Denmark) 1995, IPCO V in Vancouver (Canada) 1996, and IPCO VI in Houston (USA) 1998. IPCO is held every year in which no MPS (Mathematical Programming Society) International Symposium takes place: 1990, 1992, 1993, 1995,1996,1998,1999,2001,2002,2004,2005,2007,2008: ::::: Since the MPS meeting is triennial, IPCO conferences are held twice in everythree-year period. As a rule, in even years IPCO is held somewhere in Northern America, and in odd years it is held somewhere in Europe. In response to the call for papers for IPCO'99, the program committee - ceived99submissions, indicatingastrongandgrowinginterestintheconference.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Towards a Solution of the CornuejolsDawande Instances
1
Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts
17
Solving the Convex Cost Integer Dual Network Flow Problem
31
Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem
45
Valid Inequalities for Problems with Additive Variable Upper Bounds
60
A MinMax Theorem on Feedback Vertex Sets Preliminary Version
73
On the Separation of Maximally Violated modk Cuts
87
Improved Approximation Algorithms for Capacitated Facility Location Problems
99
The mCost ATSP
242
A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem
259
EdgeSplitting Problems with Demands
273
Integral Polyhedra Associated with Certain Submodular Functions Defined on 012Vectors
289
Optimal Compaction of Orthogonal Grid Drawings? Extended Abstract
304
On the Number of Iterations for DantzigWolfe Optimization and PackingCovering Approximation Algorithms
320
Experimental Evaluation of Approximation Algorithms for SingleSource Unsplittable Flow
328
Approximation Algorithms for a Directed Network Design Problem
345

Optimal 3Terminal Cuts and Linear Programming
114
Semidefinite Programming Methods for the Symmtric Traveling Salesman Problem
126
Bounds on the Chv atal Rank of Polytopes in the 01Cube
137
Universally Maximum Flow with PiecewiseConstant Capacities
151
Critical Extreme Points of the 2Edge Connected Spannning Subgraph Polytope
166
An Orientation Theorem with Parity Conditions
183
Parity Constrained kEdgeConnected Orientations
191
Approximation Algorithms for MAX 4SAT and Rounding Procedures for Semide
202
On the Chv atal Rank of Certain Inequalities
218
The SquareFree 2Factor Problem in Bipartite Graphs
234
Optimizing over All Combinatorial Embeddings of a Planar Graph Extended Abstract
361
A Fast Algorithm for Computing Minimum 3Way and 4Way Cuts
377
Scheduling Two Machines with Release Times
391
An Introduction to Empty Lattice Simplices
400
On Optimal EarDecompositions of Graphs
415
Strategic Issues and Applications Extended Abstract
429
Polyhedra and BranchandCut
439
Author Index
453
Copyright

Other editions - View all

Common terms and phrases