Satoru Fujishige: Submodular Functions and Optimization, Second Edition (Annals of Discrete Mathematics, Vol. 58) (Elsevier, 2005)

2nd ed. 1st ed. (1991)

Table of Contents

PART I ...... 1

Chapter I. Introduction ...... 3

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

Chapter II. Submodular Systems and Base Polyhedra ...... 21

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

Chapter III. Neoflows ...... 127

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

Chapter IV. Submodular Analysis ...... 199

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

Chapter V. Nonlinear Optimization with Submodular Constraints ...... 253

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

PART II ...... 285

Chapter VI. Submodular Function Minimization ...... 287

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

Chapter VII. Discrete Convex Analysis ...... 315

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