zbMATH — the first resource for mathematics

Geometric algorithms and combinatorial optimization. (English) Zbl 0634.05001
Algorithms and Combinatorics, 2. Berlin etc.: Springer-Verlag. xii, 362 pp.; DM 148.00 (1988).
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.
Reviewer: M. Křivánek

90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C60 Abstract computational complexity for mathematical programming problems
05C85 Graph algorithms (graph-theoretic aspects)
52B55 Computational aspects related to convexity
68Q25 Analysis of algorithms and problem complexity
90C05 Linear programming
05B35 Combinatorial aspects of matroids and geometric lattices
Full Text: EuDML