zbMATH — the first resource for mathematics

Geometric methods in combinatorial optimization. (English) Zbl 0541.90075
Progress in combinatorial optimization, Conf. Waterloo/Ont. 1982, 167-183 (1984).
[For the entire collection see Zbl 0535.00030.]
This paper states some basic algorithmic problems with respect to convex sets, polytopes and lattices. Difficulties that arise in formulating these problems are illuminated. Some results are outlined which can be obtained by applying geometric algorithms. In particular, use is made of the ellipsoid method and a method for simultaneous diophantine approximation. Moreover, applications of these results to combinatorial optimization problems are surveyed.

90C10 Integer programming
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
65K05 Numerical mathematical programming methods
11H06 Lattices and convex bodies (number-theoretic aspects)