Integer Programming and Combinatorial Optimization

1. Front Matter

   PDF

2. Colourful linear programming

   • Imre Bárány, Shmuel Onn

   Pages 1-15

3. Test sets and inequalities for integer programs

   • Rekha R. Thomas, Robert Weismantel

   Pages 16-30

4. An optimal, stable continued fraction algorithm for arbitrary dimension

   • Carsten Rössner, Claus P. Schnorr

   Pages 31-43

5. Algorithms and extended formulations for one and two facility network design

   • Sunil Chopra, Itzhak Gilboa, S. Trilochan Sastry

   Pages 44-57

6. Integer multicommodity flow problems

   • Cynthia Barnhart, Christopher A. Hane, Pamela H. Vance

   Pages 58-71

7. A heuristic algorithm for the set covering problem

   • Alberto Caprara, Matteo Fischetti, Paolo Toth

   Pages 72-84

8. An ε-Relaxation method for generalized separable convex cost network flow problems

   • Paul Tseng, Dimitri P. Bertsekas

   Pages 85-93

9. Finding real-valued single-source shortest paths in o(n ³) expected time

   • Stavros G. Kolliopoulos, Clifford Stein

   Pages 94-104

10. A network-flow technique for finding low-weight bounded-degree spanning trees

    • Sándor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young

    Pages 105-117

11. Approximating k-set cover and complementary graph coloring

    • Magnús M. Halldórsson

    Pages 118-131

12. On minimum 3-cuts and approximating k-cuts using Cut Trees

    • Sanjiv Kapoor

    Pages 132-146

13. Primal-dual approximation algorithms for feedback problems in planar graphs

    • Michel X. Goemans, David P. Williamson

    Pages 147-161

14. Cone-LP's and semidefinite programs: Geometry and a simplex-type method

    • Gábor Pataki

    Pages 162-174

15. Quadratic knapsack relaxations using cutting planes and semidefinite programming

    • C. Helmberg, F. Rendl, R. Weismantel

    Pages 175-189

16. A semidefinite bound for mixing rates of Markov chains

    • Nabil Kahale

    Pages 190-203

17. The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: Easy and hard cases

    • Rainer E. Burkard, Eranda Çela, Günther Rote, Gerhard J. Woeginger

    Pages 204-218

18. On optimizing multiplications of sparse matrices

    • Edith Cohen

    Pages 219-233

19. Continuous relaxations for Constrained Maximum-Entropy Sampling

    • Kurt M. Anstreicher, Marcia Fampa, Jon Lee, Joy Williams

    Pages 234-248

20. A submodular optimization problem with side constraints

    • David Hartvigsen

    Pages 249-259

This volume presents the proceedings of the Fifth Integer Programming and Combinatorial Optimization Conference, IPCO V, held in Vancouver, British Columbia, Canada, in June 1996.
The 36 revised papers included in the book were selected from a total of 99 submissions; they highlight recent developments in theory, computation, and applications of integer programming and combinatorial optimization. The volume is organized in sections on integer programming theory and models, network flow algorithms, approximation algorithms, semi-definite methods, matrix models, set systems and submodularity, scheduling, probabilistic methods, polyhedral methods, and the traveling salesman problem.

• Ganzzahliges Programmieren
• Handlungsreisendenproblem (TSP)
• Kombiatorische Algorithmen
• Kombinatorische Optimierung
• algorithms
• combinatorial algorithms
• combinatorial optimization
• integer programming
• programming
• scheduling
• traveling salesman problem (TSP)
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics