Geometric algorithms and combinatorial optimization (Q1210712)

The book under review thoroughly discusses two recent powerful geometric techniques -- ellipsoid method and basis reduction -- with the emphasis on the close connection between geometry and combinatorial optimization. It derives the theoretical framework for the construction of polynomial algorithms in this area. However, the attention is paid only to the polynomial solvability, not to the time optimality. The book consists of eleven chapters. After introducing the mathematical preliminaries, including basic algebraic, geometric and graph-theoretical notions in Chapter 0 the authors review the concept of computational complexity. Oracle algorithms, approximation and computation of numbers is also included. In Chapter 2 several basic computational problems for convex sets are formulated. The geometric background with the detailed description of the ellipsoid method is presented in Chapter 3. Algorithms for computing general geometric parameters of convex sets are developed in Chapter 4. The technique of basis reduction and Diophantine reduction is explained in Chapter 5. Chapter 6 is devoted to applications for rational polyhedra. The core of Chapters 7--10 is to show how the previous material can be used for a large variety of problems encountered in combinatorial optimization. This in-depth survey culminates in solutions of some problems on perfect graphs and submodular functions. The reviewer found this monograph to be very interesting, clearly and professionally written and to be a source for further researches. Everyone who is interested in geometry and combinatorial optimization should be acquainted with this thoughtful work.