Preface
Combinatorial optimization is a lively field of applied mathematics,
combining techniques from combinatorics, linear programming, and the
theory of algorithms, to solve optimization problems over discrete
structures. There are a number of classic texts in this field, but we felt
that there is a place for a new treatment of the subject, covering some of
the advances that have been made in the past decade. We set out to
describe the material in an elementary text, suitable for a one semester
course. The urge to include advanced topics proved to be irresistible, however,
and the manuscript, in time, grew beyond the bounds of what one could
reasonably expect to cover in a single course. We hope that this
is a plus for the book, allowing the instructor to pick and choose among
the topics that are treated. In this way, the book may be suitable for both
graduate and undergraduate courses, given in departments of mathematics,
operations research, and computer science. An advanced theoretical course
might spend a lecture or two on chapter 2 and sections 3.1 and 3.2, then
concentrate on 3.3, 3.4, 4.1, most of chapters 5 and 6 and some of chapters 8
and 9. An introductory course might cover chapter 2, sections 3.1 to 3.3,
section 4.1 and one of 4.2 or 4.3, and sections 5.1 through 5.3. A course
oriented more towards integer linear programming and polyhedral methods could
be based mainly on chapters 6 and 7 and would include section 3.6.
The most challenging exercises have been marked in boldface. These should
probably only be used in advanced courses.
The only real prerequisite for reading our text is a certain
mathematical maturity. We do make frequent use of linear programming
duality, so a reader unfamiliar with this subject matter
should be prepared to study the linear programming appendix before
proceeding with the main part of the text.
We benefitted greatly from thoughtful comments given by many of our
colleagues who read early drafts of the book. In particular, we would like to
thank Hernan Abeledo, Dave Applegate, Bob Bixby, Eddie Cheng, Joseph Cheriyan,
Collette Coullard, Satoru Fujishige, Grigor Gasparian, Jim Geelen, Luis Goddyn,
Michel Goemans, Mark Hartmann, Mike Juenger, Jon Lee, Tom McCormick,
Kazuo Murota, Myriam Preissmann, Irwin Pressman, Maurice Queyranne,
Andre Rohe, Andras Sebo, Eva Tardos, and Don Wagner.
Work on this book was carried out at Bellcore, the University of Bonn,
Carleton University, CWI Amsterdam, IBM Watson Research, Rice University, and
the University of Waterloo.