Submodular Functions and Optimization
- 1st Edition, Volume 47 - January 24, 1991
- Imprint: North Holland
- Author: S. Fujishige
- Language: English
- Paperback ISBN:9 7 8 - 0 - 4 4 4 - 5 5 8 4 1 - 1
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 8 6 7 8 7 - 8
The importance of submodular functions has been widely recognized in recent years in combinatorial optimization. This is the first book devoted to the exposition of the theory of… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteThe importance of submodular functions has been widely recognized in recent years in combinatorial optimization. This is the first book devoted to the exposition of the theory of submodular functions from an elementary technical level to an advanced one. A unifying view of the theory is shown by means of base polyhedra and duality for submodular and supermodular systems. Among the subjects treated are: neoflows (submodular flows, independent flows, polymatroidal flows), submodular analysis (submodular programs, duality, Lagrangian functions, principal partitions), nonlinear optimization with submodular constraints (lexicographically optimal bases, fair resource allocation). Special emphasis is placed on the constructive aspects of the theory, which lead to practical, efficient algorithms.
Introduction. 1. Mathematical Preliminaries. Submodular Systems and Base Polyhedra. 2. From Matroids to Submodular Systems. Matroids. Polymatroids. Submodular Systems. 3. Submodular Systems and Base Polyhedra. Fundamental Operations on Submodular Systems. Greedy Algorithm. Structures of Base Polyhedra. Intersecting- and Crossing-Submodular Functions. Related Polyhedra. Submodular Systems of Network Type. Neoflows. 4. The Intersection Problem. The Intersection Theorem. The Discrete Separation Theorem. The Common Base Problem. 5. Neoflows. The Equivalence of the Neoflow Problems. Feasibility for Submodular Flows. Optimality for Submodular Flows. Algorithms for Neoflows. Matroid Optimization. Submodular Analysis. 6. Submodular Functions and Convexity. Conjugate Functions and a Fenchel-Type Min-Max Theorem for Submodular and Supermodular Functions. Subgradients of Submodular Functions. The Lovász Extensions of Submodular Functions. 7. Submodular Programs. Submodular Programs - Unconstrained Optimization. Submodular Programs - Constrained Optimization. Nonlinear Optimization with Submodular Constraints. 8. Separable Convex Optimization. Optimality Conditions. A Decomposition Algorithm. Discrete Optimization. 9. The Lexicographically Optimal Base Problem. Nonlinear Weight Functions. Linear Weight Functions. 10. The Weighted Max-Min and Min-Max Problems. Continuous Variables. Discrete Variables. 11. The Fair Resource Allocation Problem. Continuous Variables. Discrete Variables. 12. The Neoflow Problem with a Separable Convex Cost Function. References. Index.
- Edition: 1
- Volume: 47
- Published: January 24, 1991
- Imprint: North Holland
- No. of pages: 269
- Language: English
- Paperback ISBN: 9780444558411
- eBook ISBN: 9780080867878
SF
S. Fujishige
Affiliations and expertise
University of Tsukuba, Institute of Socio-Economic Planning, JapanRead Submodular Functions and Optimization on ScienceDirect