Umfang:
Online-Ressource (XXIV, 696S. 78 Abb, digital)
Ausgabe:
2. Aufl. 2012
ISBN:
9783642254017
Serie:
Springer-Lehrbuch Masterclass
Inhalt:
1 Einführung -- 2 Graphen -- 3 Lineare Optimierung -- 4 Algorithmen für lineare Optimierung -- 5 Ganzzahlige Optimierung -- 6 Aufspannende Bäume und Arboreszenzen -- 7 Kürzeste Wege -- 8 Netzwerkflüsse -- 9 Flüsse mit minimalen Kosten -- 10 Maximale Matchings -- 11 Gewichtete Matchings -- 12 b-Matchings und T –Joins -- 13 Matroide -- 14 Verallgemeinerungen von Matroiden -- 15 NP-Vollständigkeit -- 16 Approximationsalgorithmen -- 17 Das Knapsack-Problem -- 18 Bin-Packing -- 19 Mehrgüterflüsse und kantendisjunkte Wege -- 20 Netzwerk-Design-Probleme -- 21 Das Traveling-Salesman-Problem -- 22 Standortprobleme -- Symbolverzeichnis -- Personenverzeichnis -- Stichwortverzeichnis.
Inhalt:
Dieses umfassende Lehrbuch über Kombinatorische Optimierung ist die deutsche Übersetzung der fünften Auflage des Buches „Combinatorial Optimization – Theory and Algorithms". Es ist aus verschiedenen Vorlesungen unterschiedlichen Niveaus (angefangen im 3. Semester des Bachelorstudiengangs) hervorgegangen, die die Autoren an der Universität Bonn gehalten haben. Das Buch legt den Schwerpunkt auf theoretische Resultate und Algorithmen mit beweisbar guten Laufzeiten und Ergebnissen. Es werden vollständige Beweise, auch für viele tiefe und neue Sätze gegeben, von denen einige bisher in der Lehrbuchliteratur noch nicht erschienen sind. Ferner enthält das Buch zahlreiche Übungsaufgaben und umfassende Literaturangaben. Diese zweite deutsche Auflage enthält alle Ergänzungen und Aktualisierungen der fünften englischen Auflage, darunter mehr als 60 neue Übungsaufgaben. Sie gibt den neuesten Stand der Kombinatorischen Optimierung wieder. Aus den Besprechungen der englischen Auflagen: "This book on combinatorial optimization is a beautiful example of the ideal textbook." Operations Research Letters 33 (2005), p.216-217 "… this very recommendable book documents the relevant knowledge on combinatorial optimization and records those problems and algorithms that define this discipline today. To read this is very stimulating for all the researchers, practitioners, and students interested in combinatorial optimization." OR News 19 (2003), p.42 "...gives an excellent comprehensive view of the exciting field of combinatorial optimization." Zentralblatt MATH 1149.90126.
Anmerkung:
Description based upon print version of record
,
AufgabenLiteratur; 3 Lineare Optimierung; 3.1 Polyeder; 3.2 Der Simplexalgorithmus; 3.3 Implementierung des Simplexalgorithmus; 3.4 Dualität; 3.5 Konvexe Hüllen und Polytope; Aufgaben; Literatur; 4 Algorithmen für lineare Optimierung; 4.1 Die Größe von Ecken und Seitenflächen; 4.2 Kettenbrüche; 4.3 Gauß-Elimination; 4.4 Die Ellipsoidmethode; 4.5 Der Satz von Khachiyan; 4.6 Separation und Optimierung; Aufgaben; Literatur; 5 Ganzzahlige Optimierung; 5.1 Die ganzzahlige Hülle eines Polyeders; 5.2 Unimodulare Transformationen; 5.3 Vollständige duale Ganzzahligkeit (TDI)
,
5.4 Vollständig-unimodulare Matrizen5.5 Schnittebenen; 5.6 Lagrange-Relaxierung; Aufgaben; Literatur; 6 Aufspannende Bäume und Arboreszenzen; 6.1 Aufspannende Bäume mit minimalem Gewicht; 6.2 Arboreszenzen mit minimalem Gewicht; 6.3 Polyedrische Darstellungen; 6.4 Das Packen von aufspannenden Bäumen und Arboreszenzen; Aufgaben; Literatur; 7 Kürzeste Wege; 7.1 Kürzeste Wege von einer Quelle aus; 7.2 Kürzeste Wege zwischen allen Knotenpaaren; 7.3 Kreise mit minimalem durchschnittlichen Kantengewicht; Aufgaben; Literatur; 8 Netzwerkflüsse; 8.1 Das Max-Flow-Min-Cut-Theorem
,
10.1 Bipartite Matchings10.2 Die Tutte-Matrix; 10.3 Der Satz von Tutte; 10.4 Ohrenzerlegungen faktorkritischer Graphen; 10.5 Edmonds' Matching-Algorithmus; Aufgaben; Literatur; 11 Gewichtete Matchings; 11.1 Das Zuordnungsproblem; 11.2 Abriss des gewichteten Matching-Algorithmus; 11.3 Implementierung des gewichteten Matching-Algorithmus; 11.4 Postoptimierung; 11.5 Das Matching-Polytop; Aufgaben; Literatur; 12 b-Matchings und T-Joins; 12.1 b-Matchings; 12.2 T-Joins mit minimalem Gewicht; 12.3 T-Joins und T-Schnitte; 12.4 Der Satz von Padberg und Rao; Aufgaben; Literatur; 13 Matroide
,
13.1 Unabhängigkeitssysteme und Matroide
,
Vorwort zur zweiten deutschen Auflage; Vorwort zur ersten deutschen Auflage; Vorwort zur fünften englischen Auflage; Vorwort zur vierten englischen Auflage; Vorwort zur dritten englischen Auflage; Vorwort zur zweiten englischen Auflage; Vorwort zur ersten englischen Auflage; Inhaltesverzeichnis; 1 Einführung; 1.1 Enumeration; 1.2 Die Laufzeit von Algorithmen; 1.3 Lineare Optimierungsprobleme; 1.4 Sortieren; Aufgaben; Literatur; 2 Graphen; 2.1 Grundlegende Definitionen; 2.2 Bäume, Kreise und Schnitte; 2.3 Zusammenhang; 2.4 Eulersche und bipartite Graphen; 2.5 Planarität; 2.6 Planare Dualität
,
8.2 Der Satz von Menger8.3 Der Edmonds-Karp-Algorithmus; 8.4 Dinic', Karzanovs, und Fujishiges Algorithmus; 8.5 Der Goldberg-Tarjan-Algorithmus; 8.6 Gomory-Hu-Bäume; 8.7 Die minimale Kapazität eines Schnittes in einem ungerichteten Graphen; Aufgaben; Literatur; 9 Flüsse mit minimalen Kosten; 9.1 Formulierung des Problems; 9.2 Ein Optimalitätskriterium; 9.3 Der Minimum-Mean-Cycle-Cancelling-Algorithmus; 9.4 Der Sukzessive-Kürzeste-Wege-Algorithmus; 9.5 Orlins Algorithmus; 9.6 Der Netzwerk-Simplexalgorithmus; 9.7 Zeitabhängige Flüsse; Aufgaben; Literatur; 10 Kardinalitätsmaximale Matchings
Weitere Ausg.:
ISBN 9783642254000
Weitere Ausg.:
Buchausg. u.d.T. Korte, Bernhard, 1938 - Kombinatorische Optimierung Berlin : Springer Spektrum, 2012 ISBN 3642254004
Weitere Ausg.:
ISBN 9783642254000
Sprache:
Deutsch
Fachgebiete:
Wirtschaftswissenschaften
,
Mathematik
Schlagwort(e):
Kombinatorische Optimierung
;
Kombinatorische Optimierung
DOI:
10.1007/978-3-642-25401-7
URL:
Volltext
(lizenzpflichtig)
Mehr zum Autor:
Vygen, Jens 1967-
Bookmarklink
