## Integer Programming and Combinatorial Optimization: 8th International IPCO Conference, Utrecht, The Netherlands, June 13-15, 2001. Proceedings, Volume 8This volume contains the papers selected for presentation at IPCO VIII, the Eighth Conference on Integer Programming and Combinatorial Optimization, Utrecht, The Netherlands, 2001. This meeting isa forum for researchers and practitioners working on various aspects of integer programming and combi- torial optimization. The aim is to present recent developments in theory, com- tation, and application 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 nit e programs. IPCO was established in 1988 when the rs t IPCO program committee was formed. The locations and years of the seven rs t IPCO conferences were: IPCO I, Waterloo (Canada) 1990, IPCO II, Pittsburgh (USA) 1992, IPCO III, - ice (Italy) 1993, IPCO IV, Copenhagen (Denmark) 1995, IPCO V, Vancouver (Canada) 1996, IPCO VI, Houston (USA) 1998, IPCO VII, Graz (Austria) 1999. IPCO is held every year in which no MPS (Mathematical Programming Society) International Symposium takes place. Since the MPS meeting is triennial, IPCO conferences are held twice in every three-year period. Asa rule, IPCO is held somewhere in Northern America in even years, and somewhere in Europe in odd years. |

### What people are saying - Write a review

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

### Contents

Two Olog kApproximation Algorithms for the Asymmetric kCenter Problem | 1 |

Strongly Polynomial Algorithms for the Unsplittable Flow Problem | 15 |

Edge Covers of Setpairs and the Iterative Rounding Method | 30 |

The Asymptotic Performance Ratio of an OnLine Algorithm for Uniform Parallel Machine Scheduling with Release Dates | 45 |

Approximate kMSTs and kSteiner Trees via the PrimalDual Method and Lagrangean Relaxation | 60 |

On the Rank of Mixed 01 Polyhedra | 71 |

Fast 2Variable Integer Programming | 78 |

Approximating kSpanner Problems for k 2 | 90 |

Synthesis of 2Commodity Flow Networks | 226 |

Bounds for Deterministic Periodic Routing Sequences | 236 |

Cutting Planes for Mixed 01 Semidefinite Programs | 251 |

Independence Free Graphs and Vertex Connectivity Augmentation | 264 |

The Throughput of Sequential Testing | 280 |

An Explicit Exact SDP Relaxation for Nonlinear 01 Programs | 293 |

Pruning by Isomorphism in BranchandCut | 304 |

Facets Algorithms and Polyhedral Characterizations for a Multiitem Production Planning Model with Setup Times | 318 |

A Matroid Generalization of the Stable Matching Polytope | 105 |

A 2Approximation for Minimum Cost 012 Vertex Connectivity | 115 |

Combined Connectivity Augmentation and Orientation Problems | 130 |

An Extension of a Theorem of Henneberg and Laman | 145 |

Bisubmodular Function Minimization | 160 |

On the Integrality Gap of a Natural Formulation of the SingleSink BuyatBulk Network Design Problem | 170 |

Circuit Mengerian Directed Graphs | 185 |

Integral Polyhedra Related to Even Cycle and Even Cut Matroids | 196 |

A Unified Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems | 210 |

On Relaxations for the Linear Ordering Problem | 333 |

Generating Cuts from MultipleTerm Disjunctions | 348 |

A 2+Approximation Algorithm for Generalized Preemptive Open Shop Problem with Minsum Objective | 361 |

Performance Guarantees of Local Search for Multiprocessor Scheduling | 370 |

Connected Joins in Graphs | 383 |

Two NPHardness Results for Preemptive Minsum Scheduling of Unrelated Parallel Machines | 396 |

Approximation Algorithms for the Minimum Bends Traveling Salesman Problem | 406 |

Author Index | 422 |

### Other editions - View all

Integer Programming and Combinatorial Optimization: 8th ..., Volume 8 Karen Aardal,A. M. H. Gerards No preview available - 2001 |

Integer Programming and Combinatorial Optimization Karen Aardal,Bert Gerards No preview available - 2014 |

### Common terms and phrases

9-division approximation algorithm assume augmentation bisection bisubmodular circuit clutter combinatorial combinatorial optimization Computer consider constraints contains convex corresponding cost cover cuts cycle deﬁne denote digraph disjoint disjunctive e-paths edge-connectivity exists extreme point feasible feedback arc set ﬁrst fractional centers given graph G Hence inequality instance integer programming integrality gap IPCO isomorphic iterative least Lemma Let G linear programming lower bound LP relaxation matrix matroid MAX-CUT maximal maximum minimal minimum node NP-hard obtained operations optimal schedule optimal solution pair parallel machines partition path polyhedra polyhedron polymatroid polynomial polytope preemptive processing Proof Proposition prove push optimal queue resp routing sequence saturating edge semidefinite semidefinite programming set function setpairs solve splitting st-path Steiner tree subgraph subset supermodular T-join Theorem traveling salesman problem undirected graph variables vector vertex vertex connectivity vertices WSPR