zbMATH — the first resource for mathematics

An algorithmic theory of numbers, graphs and convexity. (English) Zbl 0606.68039
CBMS-NSF Regional Conference Series in Applied Mathematics 50. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-203-3). iv, 91 p. (1986).
Beside the classical and the constructivist way of doing mathematics, a new challenge faces contemporary researchers: studying how much of classical results can be carried on in an efficient (i.e. polynomial) algorithmic way. Extremely difficult problems arise even for some very elementary classical facts. To cite the author, ”just think of the elementary fact, known to Euclid, that any integer has a unique prime factorization, and contrast it with the apparent intractability of the corresponding algorithmic problem, namely the problem of finding this decomposition”. The author is a champion of this approach and his present work provides an exciting introduction in the domain.
The exposition is based on the ellipsoid method and on the simultaneous diophantine approximation algorithm. Among the surveyed problems we list: the simultaneous diophantine approximation algorithm of Lenstra, Lenstra and Lovasz, some of its applications in the geometry of numbers, algorithmic problems concerning n-dimensional convex sets, a less known version of the ellipsoid method (namely shallow cuts), the polynomial- time algorithm of H. W. Lenstra for integer programming in a fixed dimension (with a new proof). The final part of these lectures discusses the possibility of polynomial algorithms for various problems of combinatorial optimization as flow problems, optimization in perfect graphs and minimization of submodular functions. Most of these topics are discussed in detail and the main ideas and paradigms are clearly outlined. The lecture notes are well written and it is a worth enjoyable time reading them.
Reviewer: M.Zimand

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
90C10 Integer programming