Submodular Functions and Optimization (eBook)
269 Seiten
Elsevier Science (Verlag)
978-0-08-086787-8 (ISBN)
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.
Front Cover 1
Submodular Functions and Optimization 4
Copyright Page 5
Contents 8
Preface 6
Chapter I. Introduction 12
1. Introduction 12
Chapter II. Submodular Systems and Base Polyhedra 28
2. From Matroids to Submodular Systems 28
3. Submodular Systems and Base polyhedra 47
Chapter III. Neoflows 120
4. The Intersection Problem 120
5. Neoflows 136
Chapter IV. Submodular Analysis 186
6. Submodular Functions and Convexity 186
7. Submodular Programs 202
Chapter V. Nonlinear Optimization with Submodular Constraints 234
8. Separable Convex Optimization 234
9. The Lexicographically Optimal Base Problem 242
10. The Weighted Max-Min and Min-Max Problems 249
11. The Fair Resource Allocation Problem 252
12. The Neoflow Problem with a Separable Convex Cost Function 259
References 262
Index 276
| Erscheint lt. Verlag | 24.1.1991 |
|---|---|
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Angewandte Mathematik |
| Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik | |
| Mathematik / Informatik ► Mathematik ► Graphentheorie | |
| Technik | |
| Wirtschaft ► Betriebswirtschaft / Management | |
| ISBN-10 | 0-08-086787-1 / 0080867871 |
| ISBN-13 | 978-0-08-086787-8 / 9780080867878 |
| Haben Sie eine Frage zum Produkt? |
PDF (Adobe DRM)Größe: 12,3 MB
Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
