目次

Introduction. 1. Mathematical Preliminaries. Submodular Systems and BasePolyhedra. 2. From Matroids to Submodular Systems. Matroids. Polymatroids.Submodular Systems. 3. Submodular Systems and Base Polyhedra. FundamentalOperations on Submodular Systems. Greedy Algorithm. Structures of BasePolyhedra. Intersecting- and Crossing-Submodular Functions. RelatedPolyhedra. Submodular Systems of Network Type. Neoflows. 4. The IntersectionProblem. The Intersection Theorem. The Discrete Separation Theorem. TheCommon Base Problem. 5. Neoflows. The Equivalence of the Neoflow Problems.Feasibility for Submodular Flows. Optimality for Submodular Flows. Algorithmsfor Neoflows. Matroid Optimization. Submodular Analysis. 6. SubmodularFunctions and Convexity. Conjugate Functions and a Fenchel-Type Min-MaxTheorem for Submodular and Supermodular Functions. Subgradients of SubmodularFunctions. The Lovasz Extensions of Submodular Functions. 7. SubmodularPrograms. Submodular Programs - Unconstrained Optimization. SubmodularPrograms - Constrained Optimization. Nonlinear Optimization with SubmodularConstraints. 8. Separable Convex Optimization. Optimality Conditions. ADecomposition Algorithm. Discrete Optimization. 9. The LexicographicallyOptimal Base Problem. Nonlinear Weight Functions. Linear Weight Functions.10. The Weighted Max-Min and Min-Max Problems. Continuous Variables. DiscreteVariables. 11. The Fair Resource Allocation Problem. Continuous Variables.Discrete Variables. 12. The Neoflow Problem with a Separable Convex CostFunction. References. Index.