Integer Programming and Combinatorial Optimization

1. Front Matter

   PDF

2. Improved approximation algorithms for MAX k-CUT and MAX BISECTION

   • Alan Frieze, Mark Jerrum

   Pages 1-13

3. Approximating minimum feedback sets and multi-cuts in directed graphs

   • Guy Even, Joseph (Seffi) Naor, Baruch Schieber, Madhu Sudan

   Pages 14-28

4. Nonlinear formulations and improved randomized approximation algorithms for multicut problems

   • Dimitris Bertsimas, Chungpiaw Teo, Rakesh Vohra

   Pages 29-39

5. Separating clique tree and bipartition inequalities in polynomial time

   • Robert D. Carr

   Pages 40-49

6. The interval order polytope of a digraph

   • Rudolf Müller, Andreas S. Schulz

   Pages 50-64

7. Separation problems for the stable set polytope

   • Eddie Cheng, William H. Cunningham

   Pages 65-79

8. Computational study of a family of mixed-integer quadratic programming problems

   • Daniel Bienstock

   Pages 80-94

9. A minimal algorithm for the Bounded Knapsack Problem

   • David Pisinger

   Pages 95-109

10. A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems

    • L. F. Escudero, S. Martello, P. Toth

    Pages 110-123

11. Combining semidefinite and polyhedral relaxations for integer programs

    • C. Helmberg, S. Poljak, F. Rendl, H. Wolkowicz

    Pages 124-134

12. Distributed near-optimal matching

    • Xiaotie Deng

    Pages 135-144

13. The random linear bottleneck assignment problem

    • Ulrich Pferschy

    Pages 145-156

14. On implementing push-relabel method for the maximum flow problem

    • Boris V. Cherkassky, Andrew V. Goldberg

    Pages 157-171

15. Use of hidden network structure in the set partitioning problem

    • Agha Iqbal Ali, Hyun-Soo Han, Jeffery L. Kennington

    Pages 172-184

16. Generalized max flows and augmenting paths

    • David Hartvigsen

    Pages 185-197

17. Oriented matroid polytopes and polyhedral fans are signable

    • Peter Kleinschmidt, Shmuel Onn

    Pages 198-211

18. On combinatorial properties of binary spaces

    • Beth Novick, András Sebő

    Pages 212-227

19. Coverings and delta-coverings

    • André Bouchet

    Pages 228-243

20. The topological structure of maximal lattice free convex bodies: The general case

    • I. Bárány, H. E. Scarf, D. Shallcross

    Pages 244-251

This volume constitutes the proceedings of the Fourth International Conference on Integer Programming and Combinatorial Optimization, IPCO '95, held in Copenhagen in May 1995 under the sponsorship of the Mathematical Programming Society.
Integer programming and combinatorial optimization provide a fruitful theoretical and algorithmic basis for the solution of a number of optimization problems occuring in real-world situations, such as production planning and scheduling, routing, crew scheduling, or network construction. This volume presents 36 revised papers selected from a total of 105 submissions and offers a representative up-to-date snapshot on the state of the art in this interdisciplinary area of research and applications.

• Algorithms
• CombinatoriaL Optimization
• Integer-Programming
• Kombinatorische Optimierung
• Mathematial Programming
• Optimerungsalgorithmen
• Optimization Algorithms
• Polyhedral
• algorithm
• optimization
• programming
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics