Integer Programming and Combinatorial Optimization: 8th International IPCO Conference, Utrecht, The Netherlands, June 13-15, 2001. Proceedings, Volume 8

Front Cover
Springer Science & Business Media, May 30, 2001 - Business & Economics - 421 pages
This 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
Copyright

Other editions - View all

Common terms and phrases