Submodular Functions and Optimization - 1st Edition - ISBN: 9780444885562, 9780080867878

Submodular Functions and Optimization, Volume 47

1st Edition

Authors: S. Fujishige
eBook ISBN: 9780080867878
Imprint: North Holland
Published Date: 24th January 1991
Page Count: 269
Tax/VAT will be calculated at check-out
72.95
43.99
54.95
Unavailable
File Compatibility per Device

PDF, EPUB, VSB (Vital Source):
PC, Apple Mac, iPhone, iPad, Android mobile devices.

Mobi:
Amazon Kindle eReader.

Institutional Access


Table of Contents

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.


Description

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 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.


Details

No. of pages:
269
Language:
English
Copyright:
© North Holland 1991
Published:
Imprint:
North Holland
eBook ISBN:
9780080867878

Reviews

@qu:...a well-designed book containing a wealth of very interesting results. The book can be used as a reference book and as a source for a reading class. @source:Zentralblatt für Mathematik


About the Authors

S. Fujishige Author

Affiliations and Expertise

University of Tsukuba, Institute of Socio-Economic Planning, Japan