Combinatorial optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank and Alexander Schrijver, Wiley, New York, 1998. ISBN 0-471-55894-X. No. of pages: 355. Price: £24.95.

✍ Scribed by V. J. Rayward-Smith

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 16 KB
• Volume: 11
• Category: Article
• ISSN: 0894-3370
• DOI: 10.1002/(sici)1099-1204(199809/10)11:5<273::aid-jnm304>3.0.co;2-d

✦ Synopsis

Combinatorial optimization is one of the most active areas of applied mathematics, with wide application throughout industry and commerce. It is taught in both undergraduate and postgraduate courses within mathematics, OR and computer science departments.

This text, written by some of the most respected researchers in the field, contains both the classic, core material and also some of the more recent, advanced material. It is a lovely, lovely book, a joy to read and should rapidly become established as a leading textbook.

The reader will need to have a sound understanding of discrete mathematics and to be familiar with linear programming. The book will then be understood quite easily. Not only are there good descriptions of the classic graph algorithms (minimum spanning tree, maximum flow, shortest paths, Euler graphs, etc.) but also clear expositions of some of the more difficult material in this area. Edmond's matching algorithm, for example, receives one of the clearest explanations that I have seen.

The chapter on Integrality of Polyhedra is probably the most difficult in the book. However, in just over 40 pages the reader will be able to master the basics of this important topic. Another chapter on advanced material is that on matroids but, with a simple introduction via Kruskal's MST algorithm, the reader quickly finds himself or herself appreciating the basics of matroid theory. The matroid-intersection algorithm and weighted matroid-intersection algorithm are derived without difficulty.

The Travelling Salesman problem is one of the most famous problems in combinatorial optimization.