DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Twenty
TITLE: Combinatorial Optimization: Papers from the DIMACS Special Year
EDITORS: William Cook, Laszlo Lovasz, Paul Seymour
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.

PREFACE

The fourth special year of DIMACS, in 1992/93, was devoted to combinatorial optimization. During the special year, a number of workshops, small and large, were devoted to various aspects of this main theme. Some were devoted to well established, large topics; some, to special problems; and some, to fresh ideas and freshly discovered connections between combinatorial optimization and other areas, often quite distant.

It seemed to us that the best way to document this activity is not by editing proceedings of selected workshops, but by asking organizers and/or participants to write surveys on those topics they felt were the most central or most exciting. The response was very positive and resulted in the survey articles collected in this volume.

Table of Contents

Forward ix
Preface xi
Hypermetrics in geometry of numbers

    M.Deza, V.P. Grishukhin, M. Laurent

 1
Practical problem solving with cutting plane algorithms in combinatorial optimization

    Michael Junger, Gerhard Reinelt, Stefan Thienel

 111
Randomized algorithms in combinatorial optimization

    Laszlo Lovasz

 153
Maximum cuts and largest bipartite subgraphs

    Svatopluk Poljak, Zsolt Tuza

 181
Algorithms and reformulations for lot sizing problems

    Yves Pochet, Laurence A. Wolsey

 245
Efficient algorithms for disjoint paths in planar graphs

    Heike Ripphausen-Lipa, Dorothea Wagner, Karsten Weihe

 295
Computing near-optimal solutions to combinatorial optimization problems

    David B. Shmoys

 355
Graph entropy: A survey

    Gagor Simonyi

 399
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.