Submodular Functions and Optimization (Volume 58) (Annals of Discrete Mathematics, Volume 58)

✍ Scribed by Satoru Fujishige

• Publisher: Elsevier Science
• Year: 2005
• Tongue: English
• Leaves: 409
• Edition: 2
• Category: Library

✦ Synopsis

It has widely been recognized that submodular functions play essential roles in efficiently solvable combinatorial optimization problems. Since the publication of the 1st edition of this book fifteen years ago, submodular functions have been showing further increasing importance in optimization, combinatorics, discrete mathematics, algorithmic computer science, and algorithmic economics, and there have been made remarkable developments of theory and algorithms in submodular functions. The 2nd edition of the book supplements the 1st edition with a lot of remarks and with new two chapters: "Submodular Function Minimization" and "Discrete Convex Analysis." The present 2nd edition is still a unique book on submodular functions, which is essential to students and researchers interested in combinatorial optimization, discrete mathematics, and discrete algorithms in the fields of mathematics, operations research, computer science, and economics.

• Self-contained exposition of the theory of submodular functions
• Selected up-to-date materials substantial to future developments
• Polyhedral description of Discrete Convex Analysis
• Full description of submodular function minimization algorithms
• Effective insertion of figures
• Useful in applied mathematics, operations research, computer science, and economics

✦ Table of Contents

Cover
Series
Title page
Date-line
Preface
Preface to the Second Edition
Contents
PART I
Chapter I. Introduction
1. Introduction
1.1. Introduction
1.2. Mathematical Preliminaries
(a) Sets
(b) Algebraic structures
(c) Graphs
(d) Network flows
(e) Elements of convex analysis and linear inequalities
Chapter II. Submodular Systems and Base Polyhedra
2. From Matroids to Submodular Systems
2.1. Matroids
2.2. Polymatroids
2.3. Submodular Systems
3. Submodular Systems
3.1. Fundamental Operations on Submodular Systems
(a) Reductions and contractions by sets
(b) Reductions and contractions by vectors
(c) Translations and sums
(d) Other operations
3.2. Greedy Algorithm
(a) Distributive lattices and posets
(b) Greedy algorithm
3.3. Structures of Base Polyhedra
(a) Extreme points and rays
(b) Elementary transformations of bases
(c) Tangent cones
(d) Faces, dimensions and connected components
3.4. Intersecting- and Crossing-Submodular Functions
(a) Tree representations of cross-free families
(b) Crossing-submodular functions
(c) Intersecting-submodular functions
3.5. Related Polyhedra
(a) Generalized polymatroids
(b) Polypseudomatroids
(c) Ternary semimodular polyhedra
3.6. Submodular Systems of Network Type
Chapter III. Neoflows
4. The Intersection Problem
4.1. The Intersection Theorem
(a) Preliminaries
(b) An algorithm and the intersection theorem
(c) A refinement of the algorithm
4.2. The Discrete Separation Theorem
4.3. The Common Base Problem
5. Neoflows
5.1. Neoflows
(a) Submodular flows
(b) Independent flows
(c) Polymatroidal flows
5.2. The Equivalence of the Neoflow Problems
(a) From submodular flows to independent flows
(b) From independent flows to polymatroidal flows
(c) From polymatroidal flows to submodular flows
5.3. Feasibility for Submodular Flows
5.4. Optimality for Submodular Flows
5.5. Algorithms for Neoflows
(a) Maximum independent flows
(b) Maximum submodular flows
(c) Minimum-cost submodular flows
5.6. Matroid Optimization
(a) Maximum independent matchings
(b) Optimal independent assignments
Chapter IV. Submodular Analysis
6. Submodular Functions and Convexity
6.1. Conjugate Functions and a Fenchel-Type Min-Max Theorem for Submodular and Supermodular Functions
(a) Conjugate functions
(b) A Fenchel-type min-max theorem
6.2. Subgradients of Submodular Functions
(a) Subgradients and subdifferentials
(b) Structures of subdifferentials
6.3. The Lovasz Extensions of Submodular Functions
7. Submodular Programs
7.1. Submodular Programs — Unconstrained Optimization
(a) Minimizing submodular functions
(b) Minimizing modular functions
7.2. Submodular Programs — Constrained Optimization
(a) Lagrangian functions and optimality conditions
(b) Related problems
(b.1) The principal partition
(b.2) The principal structures of submodular systems
(b.3) The minimum-ratio problem
Chapter V. Nonlinear Optimization with Submodular Constraints
8. Separable Convex Optimization
8.1. Optimality Conditions
8.2. A Decomposition Algorithm
8.3. Discrete Optimization
9. The Lexicographically Optimal Base Problem
9.1. Nonlinear Weight Functions
9.2. Linear Weight Functions
10. The Weighted Max-Min and Min-Max Problems
10.1. Continuous Variables
10.2. Discrete Variables
11. The Fair Resource Allocation Problem
11.1. Continuous Variables
11.2. Discrete Variables
12. The Neoflow Problem with a Separable Convex Cost Function
PART II
Chapter VI. Submodular Function Minimization
13. Symmetric Submodular Function Minimization: Queyranne's Algorithm
14. Submodular Function Minimization
14.1. The Iwata-Fleischer-Fujishige Algorithm
(a) A weakly polynomial algorithm
(b) A strongly polynomial algorithm
(c) Modification with multiple exchanges
(d) Submodular functions on distributive lattices
14.2. Schrijver's Algorithm
14.3. Further Progress in Submodular Function Minimization
Chapter VII. Discrete Convex Analysis
15. Locally Polyhedral Convex Functions and Conjugacy
16. L- and L$^\natural$-convex Functions
16.1. L- and L$^\natural$-convex Sets
16.2. L- and L$^\natural$-convex Functions
16.3. Domain-integral L- and L$^\natural$-convex Functions
17. M- and M* -convex Functions
18. Conjugacy between L-/L$^\natural$-convex Functions and M-/M$^\natural$-convex Functions
19. The Discrete Fenchel-Duality Theorem
20. Algorithmic and Structural Properties of Discrete Convex Function
20.1. L- and L$^\natural$-convex Functions
20.2. M- and M$^\natural$-convex Functions
20.3. Proximity Theorems
21. Other Related Topics
21.1. The M-convex Submodular Flow Problem
21.2. A Two-sided Discrete-Concave Market Model
22. Historical Notes
References
Index