Submodular Functions and Optimization

✍ Scribed by Satoru Fujishige (Eds.)

• Publisher: North-Holland
• Year: 1991
• Tongue: English
• Leaves: 281
• Series: Annals of discrete mathematics 47
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Content:
General Editor
Page ii

Edited by
Page iii

Copyright page
Page iv

Preface
Pages v-vi
S.F.

Chapter I. Introduction
Pages 1-16

Chapter II. Submodular Systems and Base Polyhedra
Pages 17-108

Chapter III. Neoflows
Pages 109-173

Chapter IV. Submodular Analysis
Pages 175-222

Chapter V. Nonlinear Optimization with Submodular Constraints
Pages 223-250

References
Pages 251-264

Index
Pages 265-270