## Integer Programming and Combinatorial Optimization: 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, ProceedingsThis 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 |

453 | |

### Other editions - View all

### Common terms and phrases

2-matching 2-way cut algorithm for MAX approximation algorithm capacity Chvátal Chvátal rank combinatorial optimization components compute consider constraints contains contradiction convex Cornuéjols corresponding cost cycle deﬁned denote edge exists extreme point facet feasible solution feedback vertex set ﬁow ﬁrst function given graph G greedy-type hence implies incidence vector inequality instances Integer Programming least Lemma Let G linear programming Lovász lower bound Mathematics matrix MAX 4-SAT maximum flow maximum flow problem minimal minimum 2-way mod-k cut network flow network flow problem node nonnegative NP-hard obtained optimal solution pair partition path planar graph polyhedra polyhedron polynomial polytope Proof prove relaxation result rounding procedure satisﬁes satisfy semidefinite programming solve split SPQR-tree subgraph submodular subset subtour supermodular Suppose symmetric Theorem tight traveling salesman problem tree undirected graph upper bound v-tree valid variables vertices weight