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.