Submodular functions and optimization (Q1188800)

The author presents a summary of many results in the theory on submodular functions and optimization algorithms obtained in the recent past. The keys in his approach are the concepts of base polyhedra and duality for submodular and supermodular systems. After a short review of definitions and results in algebra, graph theory, and systems of linear inequalities, which are relevant for the following chapters, the second chapter is devoted to submodular systems and base polyhedra. This chapter shows the development of generalization from matroids over polymatroids to submodular systems. Results in the former two areas are quoted without proofs, but the theory of submodular systems - including the discussion of base polyhedra and duality - is discussed in full length. Based on the observation that an equivalence between submodular flows, independent flows and polymatroid flows can be established, neoflows, general flows in this equivalence class, are investigated. Feasibility questions, optimality criteria, algorithms, and applications to matroid optimization problems are discussed. The fourth chapter deals with the relation between submodular functions on distributive lattices on one hand and convex functions on convex sets on the other hand. It is shown that both systems have many similarities which can be explored. Consequently, submodular programs, i.e. optimization problems with objective functions and constraints described by submodular functions, can be tackled by powerful methods. Nonlinear optimization with submodular constraints is the topic of the last chapter. This chapter contains results on separable convex optimization, the lexicographically optimal base problem, and the weighted max-min and min-max problem. The book is a self-contained introduction to the field of submodular functions. The main emphasis of the book is on a unifying view of the author on submodular functions using base polyhedra and duality, and not on complexity questions of algorithms. Reading the book is certainly a pleasure, but - at least for most of us - it should not be planned as a leisure activity. The author rewards readers who are willing to invest enough effort with a well-designed book containing a wealth of very interesting results. The book can be used as a reference book and as a source for a reading class.