2nd ed.
1st ed. (1991)
1. Introduction ...... 3
1.1. Introduction ...... 3
1.2. Mathematical Preliminaries ...... 4
(a) Sets ...... 4
(b) Algebraic structures ...... 5
(c) Graphs ...... 9
(d) Network flows ...... 13
(e) Elements of convex analysis and linear inequalities ...... 15
2. From Matroids to Submodular Systems ...... 21
2.1. Matroids ...... 21
2.2. Polymatroids ...... 25
2.3. Submodular Systems ...... 33
3. Submodular Systems and Base Polyhedra ...... 45
3.1. Fundamental Operations on Submodular Systems ...... 45
(a) Reductions and contractions by sets ...... 45
(b) Reductions and contractions by vectors ...... 46
(c) Translations and sums ...... 51
(d) Other operations ...... 53
3.2. Greedy Algorithm ...... 55
(a) Distributive lattices and posets ...... 55
(b) Greedy algorithm ...... 58
3.3. Structures of Base Polyhedra ...... 66
(a) Extreme points and rays ...... 66
(b) Elementary transformations of bases ...... 70
(c) Tangent cones ...... 72
(d) Faces, dimensions and connected components ...... 75
3.4. Intersecting- and Crossing-Submodular Functions ...... 86
(a) Tree representations of cross-free families ...... 87
(b) Crossing-submodular functions ...... 91
(c) Intersecting-submodular functions ...... 101
3.5. Related Polyhedra ...... 102
(a) Generalized polymatroids ...... 102
(b) Polypseudomatroids ...... 106
(c) Ternary semimodular polyhedra ...... 112
3.6. Submodular Systems of Network Type ...... 122
4. The Intersection Problem ...... 127
4.1. The Intersection Problem ...... 127
(a) Preliminaries ...... 128
(b) An algorithm and the intersection theorem ...... 131
(c) A refinement of the algorithm ...... 136
4.2. The Discrete Separation Theorem ...... 140
4.3. The Common Base Problem ...... 142
5. Neoflows ...... 145
5.1. Neoflows ...... 145
(a) Submodular flows ...... 145
(b) Independent flows ...... 146
(c) Polymatroidal flows ...... 147
5.2. The Equivalence of the Neoflow Problems ...... 148
(a) From submodular flows to independent flows ...... 148
(b) From independent flows to polymatroidal flows ...... 149
(c) From polymatroidal flows to submodular flows ...... 150
5.3. Feasibility for Submodular Flows ...... 153
5.4. Optimality for Submodular Flows ...... 155
5.5. Algorithms for Neoflows ...... 167
(a) Maximum indepedent flows ...... 167
(b) Maximum submodular flows ...... 172
(c) Minimum-cost submodular flows ...... 175
5.6. Matroid Optimization ...... 188
(a) Maximum independent matchings ...... 188
(b) Optimal independent assignments ...... 194
6. Submodular Functions and Convexity ...... 199
6.1. Conjugate Functions and a Fenchel-Type Min-Max Theorem for Submodular and Supermodular Functions ...... 199
(a) Conjugate functions ...... 199
(b) A Fenchel-type min-max theorem ...... 201
6.2. Subgradients of Submodular Functions ...... 203
(a) Subgradients and subdifferentials ...... 203
(b) Structures of subdifferentials ...... 209
6.3. The Lovasz Extensions of Submodular Functions ...... 211
7. Submodular Programs ...... 216
7.1. Submodular Programs --- Unconstrained Optimization ...... 216
(a) Minimizing submodular functions ...... 217
(b) Minimizing modular functions ...... 223
7.2. Submodular Programs --- Constrained Optimization ...... 228
(a) Lagrangian functions and optimality conditions ...... 229
(b) Related problems ...... 234
(b.1) The principal partition ...... 234
(b.2) The principal structures of submodular systems ...... 245
(b.3) The minimum-ratio problem ...... 248
8. Separable Convex Optimization ...... 253
8.1. Optimality Conditions ...... 253
8.2. A Decomposition Algorithm ...... 257
8.3. Discrete Optimization ...... 260
9. The Lexicographically Optimal Base Problem ...... 261
9.1. Nonlinear Weight Functions ...... 262
9.2. Linear Weight Functions ...... 264
10. The Weighted Max-Min and Min-Max Problems ...... 269
10.1. Continuous Variables ...... 269
10.2. Discrete Variables ...... 272
11. The Fair Resource Allocation Problem ...... 273
11.1. Continuous Variables ...... 273
11.2. Discrete Variables ...... 274
12. The Neoflow problem with a Separable Convex Cost Function ...... 280
13. Symmetric Submodular Function Minimization: Queyranne's Algorithm ...... 287
14. Submodular Function Minimization ...... 290
14.1. The Iwata-Fleischer-Fujishige Algorithm ...... 293
(a) A weakly polynomial algorithm ...... 293
(b) A strongly polynomial algorithm ...... 300
(c) Modification with multiple exchanges ...... 303
(d) Submodular functions on distributive lattices ...... 305
14.2. Schrijver's Algorithm ...... 308
14.3. Further Progress in Submodular Function Minimization ...... 313
15. Locally Polyhedral Convex Functions and Conjugacy ...... 315
16. L- and L${}^\natural$-convex Functions ...... 319
16.1. L- and L${}^\natural$-convex Sets ...... 319
16.2. L- and L${}^\natural$-convex Functions ...... 322
16.3. Domain-integral L- and L${}^\natural$-convex Functions ...... 326
17. M- and M${}^\natural$-convex Functions ...... 331
18. Conjugacy between L-/L${}^\natural$-convex Functions and M-/M${}^\natural$-convex Functions ...... 338
19. The Discrete Fenchel-Duality Theorem ...... 341
20. Algorithmic and Structural Properties of Discrete Convex Functions ...... 344
20.1. L- and L${}^\natural$-convex Functions ...... 344
20.2. M- and M${}^\natural$-convex Functions ...... 345
20.3. Proximity Theorems ...... 351
21. Other Related Topics ...... 356
21.1. The M-convex Submodular Flow Problem ...... 356
21.2. A Two-sided Discrete-Concave Market Model ...... 357
22. Historical Notes ...... 360
References ...... 365
Index ...... 389