5. IPCO 1996: Vancouver, BC, Canada

William H. Cunningham, S. Thomas McCormick, Maurice Queyranne (Eds.): Integer Programming and Combinatorial Optimization, 5th International IPCO Conference, Vancouver, British Columbia, Canada, June 3-5, 1996, Proceedings. Lecture Notes in Computer Science 1084 Springer 1996, ISBN 3-540-61310-2

Session 1: Integer Programming Theory

Imre Bárány, Shmuel Onn:
Colourful Linear Programming. 1-15
Rekha R. Thomas, Robert Weismantel:
Test Sets and Inequalities for Integer Programs. 16-30
Carsten Rössner, Claus-Peter Schnorr:
An Optimal, Stable Continued Fraction Algorithm. 31-43

Session 2: Integer Programming Models

Sunil Chopra, Itzhak Gilboa, S. Trilochan Sastry:
Algorithms and Extended Formulations for One and Two Facility Network Design. 44-57
Cynthia Barnhart, Christopher A. Hane, Pamela H. Vance:
Integer Muticommodity Flow Problems. 58-71
Alberto Caprara, Matteo Fischetti, Paolo Toth:
A Heuristic Algorithm for the Set Covering Problem. 72-84

Session 3: Network Flow Algorithms

Paul Tseng, Dimitri P. Bertsekas:
A epsilon-Relaxation Method for Generalized Separable Convex Cost Network Flow Problems. 85-93
Stavros G. Kolliopoulos, Clifford Stein:
Finding Real-Valued Single-Source Shortest Paths. 94-104
Sándor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal E. Young:
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees. 105-117

Session 4: Approximation Algorithms

Magnús M. Halldórsson:
Approximating k-Set Cover and Complementary Graph Coloring. 118-131
Sanjiv Kapoor:
On Minimum 3-Cuts and Approximating k-Cuts Using Cut Trees. 132-146
Michel X. Goemans, David P. Williamson:
Primal-Dual Approximation Algorithms for Feedback Problems. 147-161

Session 5: Semi-Definite Methods

Gábor Pataki:
Cone-LP's and Semidefinite Programs: Geometry. 162-174
Christoph Helmberg, Franz Rendl, Robert Weismantel:
Quadratic Knapsack Relaxations Using Cutting Planes. 175-189
Nabil Kahale:
A Semidefinite Bound for Mixing Rates of Markov Chains. 190-203

Session 6: Matrix Models

Rainer E. Burkard, Eranda Çela, Günter Rote, Gerhard J. Woeginger:
The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases. 204-218
Edith Cohen:
On Optimizing Multiplications of Sparse Matrices. 219-233
Kurt M. Anstreicher, Marcia Fampa, Jon Lee, Joy Williams:
Continuous Relaxations for Constrained Maximum-Entropy Sampling. 234-248

Session 7: Set Systems and Submodularity

David Hartvigsen:
A Submodular Optimization Problem with Side Constraints. 249-259
Kazuo Murota:
Convexity and Steinitz's Exchange Property. 260-274
Beth Novick, András Sebö:
On Ideal Clutters, Metrics and Multiflows. 275-287

Session 8: Scheduling I

Michel X. Goemans:
A Supermodular Relaxation for Scheduling with Release Dates. 288-300
Andreas S. Schulz:
Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds. 301-315
Neil Simonetti, Egon Balas:
Implementation of a Linear Time Algorithm for Certain Generalized Traveling Salesman Problems. 316-329

Session 9: Probabilistic Methods

Dimitris Bertsimas, Chung-Piaw Teo, Rakesh Vohra:
On Dependent Randomized Rounding Algorithms. 330-344
Hui Chen, Alan M. Frieze:
Coloring Bipartite Hypergraphs. 345-358
Chung-Piaw Teo, Dimitris Bertsimas:
Improved Randomized Approximation Algorithms for Lot-Sizing Problems. 359-373

Session 10: Scheduling II

Han Hoogeveen, Tsuyoshi Kawaguchi:
Minimizing Total Completion Time in a Two-Machine Flowshop: Analysis of Special Cases. 374-388
Paul Martin, David B. Shmoys:
A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem. 389-403
Han Hoogeveen, Arjen P. A. Vestjens:
Optimal On-Line Algorithms for Single-Machine Scheduling. 404-414

Session 11: Polyhedral Methods

Michel X. Goemans, Leslie A. Hall:
The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown. 415-429
Rudolf Müller, Andreas S. Schulz:
Transitive Packing. 430-444
Meinrad Funke, Gerhard Reinelt:
A Polyhedral Approach to the Feedback Vertex Set Problem. 445-459

Session 12: The Travelling Salesman Problem

Robert Carr:
Separating over Classes of TSP Inequalities Defined by 0 Node-Lifting in Polynominal Time. 460-474
Lisa Fleischer, Éva Tardos:
Separating Maximally Violated Comb Inequalities in Planar Graphs. 475-489
Rainer E. Burkard, Vladimir G. Deineko, Gerhard J. Woeginger:
The Travelling Salesman and the PQ-Tree. 490-504

Last update Tue Feb 14 04:04:38 2012 CET by the DBLP Team —

This material is Open Data

Data released under the ODC-BY 1.0 license — See also our legal information page