Submodular functions and convexity. (English) Zbl 0566.90060

Mathematical programming, 11th int. Symp., Bonn 1982, 235-257 (1983).
[For the entire collection see Zbl 0533.00035.]
The author shows that submodular set functions play a similar role in discrete optimization as convex functions in continuous optimization. In particular, a polynomial time algorithm to find the minimum of a submodular set function can be obtained. After giving some basic definitions and many examples from different fields the author turns to operations on submodular functions, which yield new submodular functions. In particular extensions of submodular functions are summarized. Then integrality properties of polyhedra related to submodular functions are derived and further results (for example the Matroid Intersection Theorem) are outlined. In the subsequent two sections the author shows the close relationship between submodular and convex functions on the one side and moreover that submodular functions resemble also features of concave functions. Finally optimization problems with submodular objective functions are discussed in short, in particular the submodular flow problem. Open problems and hints for further research conclude this survey paper.
Reviewer: R.E.Burkard


90C10 Integer programming
52Bxx Polytopes and polyhedra
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
05B35 Combinatorial aspects of matroids and geometric lattices


Zbl 0533.00035