ENGLISH

Submodular Functions and Optimization

By Satoru Fujishige (Eds.)

Book information

Publisher
North-Holland; Distributors for the U.S.A. and Canada, Elsevier Science Pub. Co
Year
1991
ISBN
978-0-444-88556-2, 0444885560
Language
english
Format
DJVU
Filesize
3 MB (2827214 bytes)
Series
Annals of discrete mathematics 47
Pages
ii-vi, 1-270\281
Time added
2010-02-18 13:16:04

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

Similar books