nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Kombinatorische Optimierung

Theorie und Algorithmen

verfasst von: Prof. Dr. Bernhard Korte, Prof. Dr. Jens Vygen

Verlag: Springer Berlin Heidelberg

Buchreihe : Springer-Lehrbuch Masterclass

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Dieses umfassende Lehrbuch über Kombinatorische Optimierung ist die deutsche Übersetzung der sechsten 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 dritte deutsche Auflage wurde entsprechend der sechsten englischen Auflage aktualisiert, überarbeitet und ergänzt. Es gibt unter anderem neue Abschnitte zu seichten leichten Bäumen, der Maximierung submodularer Funktionen, geglätteter Analyse vom Knapsack-Problem, der (ln 4 + ɛ)-Approximation von Steinerbäumen und dem VPN Problem.

Aus 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

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Einführung

Zusammenfassung

Wir beginnen mit einigen Beispielen und grundlegenden Definitionen, so zum Beispiel zur Laufzeit von Algorithmen.

Bernhard Korte, Jens Vygen

Kapitel 2. Graphen

Zusammenfassung

Graphen sind fundamentale kombinatorische Strukturen, die überall in diesem Buch vorkommen. In diesem Kapitel werden wir nicht nur die grundlegenden Definitionen und die Standardnotation einführen, sondern auch einige fundamentale Sätze und Algorithmen beweisen bzw. beschreiben.

Bernhard Korte, Jens Vygen

Kapitel 3. Lineare Optimierung

Zusammenfassung

In diesem Kapitel werden wir die wichtigsten Definitionen und Resultate der linearen Optimierung zusammenstellen. Darunter sind etwas Polyedertheorie, der Simplexalgorithmus und der Dualitätssatz.

Bernhard Korte, Jens Vygen

Kapitel 4. Algorithmen für lineare Optimierung

Zusammenfassung

Wir beweisen, dass sich lineare Gleichungssysteme (mit Gauß-Elimination) und lineare Programme (mit der Ellipsoidmethode) in polynomieller Zeit lösen lassen.

Wir gehen auch auf die Äquivalenz von Separation und Optimierung ein.

Bernhard Korte, Jens Vygen

Kapitel 5. Ganzzahlige Optimierung

Zusammenfassung

In diesem Kapitel betrachten wir lineare Programme mit ganzzahligen Nebenbedingungen. Unter bestimmten Bedingungen existieren immer optimale ganzzahlige Lösungen. Außerdem betrachten wir Schnittebenenverfahren und Lagrange-Relaxierung.

Bernhard Korte, Jens Vygen

Kapitel 6. Aufspannende Bäume und Arboreszenzen

Zusammenfassung

Wir betrachten die wichtigen Probleme, optimale aufspannende Bäume und Arboreszenzen zu finden.

Neben effizienten Algorithmen betrachten wir auch Beschreibungen als lineare Programme und behandeln das Packen von Bäumen.

Bernhard Korte, Jens Vygen

Kapitel 7. KürzesteWege

Zusammenfassung

Eines der bekanntesten kombinatorischen Optimierungsprobleme ist, einen kürzesten Weg zwischen zwei bestimmten Knoten eines gerichteten oder ungerichteten Graphen zu finden. Wir behandeln Algorithmen für verschiedene Varianten des Problems.

Bernhard Korte, Jens Vygen

Kapitel 8. Netzwerkflüsse

Zusammenfassung

In diesem Kapitel suchen wir einen maximalen Fluss in einem Netzwerk oder auch einen minimalen Schnitt.

Beide Probleme sind wegen des berühmten Max-Flow-Min-Cut-Theorems eng verwandt. Wir behandeln diverse Algorithmen, aber auch Anwendungen wie den Satz von Menger.

Bernhard Korte, Jens Vygen

Kapitel 9. Flüsse mit minimalen Kosten

Zusammenfassung

Auch kostenminimale Flüsse können effizient gefunden werden, wie wir in diesem Kapitel zeigen. Neben Optimalitätskriterien und schnellen Algorithmen behandeln wir auch eine Anwendung auf zeitabhängige Flüsse.

Bernhard Korte, Jens Vygen

Kapitel 10. Kardinalitätsmaximale Matchings

Zusammenfassung

In diesem Kapitel zeigen wir, wie ein Matching maximaler Kardinalität in einem Graphen in polynomieller Zeit gefunden werden kann. Dies ist in bipartiten Graphen wesentlich einfacher als in allgemeinen. Einige Struktursätze haben grundlegende Bedeutung in der kombinatorischen Optimierung.

Bernhard Korte, Jens Vygen

Kapitel 11. Gewichtete Matchings

Zusammenfassung

Das Problem, ein Matching maximalen Gewichts in einem allgemeinen Graphen zu finden, ist schwierig, kann aber dank Edmonds’ Algorithmus in polynomieller Zeit gelöst werden. Daraus folgen auch polyedrische Beschreibungen.

Bernhard Korte, Jens Vygen

Kapitel 12. b-Matchings und T-Joins

Zusammenfassung

Wir behandeln zwei Verallgemeinerungen von Matchings: b-Matchings und T-joins. Beiden ist gemeinsam, dass sie sich auf das klassische Matching-Problem zurückführen lassen.

Bernhard Korte, Jens Vygen

Kapitel 13. Matroide

Zusammenfassung

Matroide sind eine grundlegende Struktur der diskreten Optimierung, für die der Greedy-Algorithmus immer eine optimale Lösung findet. Auch eine maximal gewichtete Menge im Durchschnitt zweier Matroide kann noch effizient gefunden werden.

Bernhard Korte, Jens Vygen

Kapitel 14. Verallgemeinerungen von Matroiden

Zusammenfassung

Greedoide und Polymatroide verallgemeinern gewissermaßen Matroide. Wir behandeln auch die Minimierung und Maximierung submodularer Funktionen. Für erstere ist ein polynomieller Algorithmus bekannt. Für letztere nicht, immerhin können submodulare Funktionen aber bis auf einen Faktor 2 maximiert werden.

Bernhard Korte, Jens Vygen

Kapitel 15. NP-Vollständigkeit

Zusammenfassung

Für viele kombinatorische Optimierungsprobleme gibt es polynomielle Algorithmen; die wichtigsten unter ihnen werden in diesem Buch besprochen. Es gibt jedoch auch viele wichtige Probleme, für die kein polynomieller Algorithmus bekannt ist. Obwohl wir nicht beweisen können, dass es diese nicht gibt, können wir aber zeigen, dass aus der Existenz eines polynomiellen Algorithmus für ein „schweres“ (genauer: NP-schweres) Problem die Existenz eines polynomiellen Algorithmus für fast alle in diesem Buch besprochenen Probleme (genauer: alle NP-leichten Probleme) folgt.

Bernhard Korte, Jens Vygen

Kapitel 16. Approximationsalgorithmen

Zusammenfassung

In diesem Kapitel führen wir den wichtigen Begriff des Approximationsalgorithmus ein. Wir geben zahlreiche Beispiele (u.a. Set Covering, Max-Cut, MAX-SAT) und gehen auch auf Nichtapproximierbarkeit ein.

Bernhard Korte, Jens Vygen

Kapitel 17. Das Knapsack-Problem

Zusammenfassung

Das Knapsack-Problem ist gewissermaßen das einfachste NP-schwere Problem. Wir geben unter anderem ein voll polynomielles Approximationsschema an und führen eine geglätte Analyse durch, die zeigt, dass man das Problem in der Praxis oft optimal lösen kann.

Bernhard Korte, Jens Vygen

Kapitel 18. Bin-Packing

Zusammenfassung

Bin Packing ist ein weiteres interessantes NP-schweres Optimierungsproblem. Wir zeigen unter anderem das voll polynomielle asymptotische Approximationsschema von Karmarkar und Karp.

Bernhard Korte, Jens Vygen

Kapitel 19. Mehrgüterflüsse und kantendisjunkte Wege

Zusammenfassung

Mehrgüterflüsse und das Kantendisjunkte-Wege-Problem sind Themen dieses Kapitels. Wir betrachten unter anderem die Algorithmen von Garg-Könemann und Leighton-Rao. Außerdem studieren wir, in welchen Fällen das Kantendisjunkte-Wege-Problem polynomiell lösbar ist.

Bernhard Korte, Jens Vygen

Kapitel 20. Netzwerk-Design-Probleme

Zusammenfassung

Wie kann man günstige Teilgraphen mit bestimmten Zusammenhangseigenschaften konstruieren? Das Steinerbaumproblem ist der bekannteste Fall; wir geben den (In 4 + ϵ) – Approximationsalgorithmus an. Für allgemeines Netzwerkdesign betrachten wir einen primal-dualen Approximationsalgorithmus und Jains Algorithmus mit iterativem Runden. Ein anderes Problem, das als VPN-Problem bekannt ist, kann sogar optimal gelöst werden.

Bernhard Korte, Jens Vygen

Kapitel 21. Das Traveling-Salesman-Problem

Zusammenfassung

Das Rundreiseproblem, oder Traveling-Salesman-Problem, ist wohl das berühmteste NP-schwere kombinatorische Optimierungsproblem. Wir behandeln neben Approximationslagorithmen und polyedrischen Beschreibungen auch Heuristiken und untere Schranken, die Grundlagen für eine Lösung großer Instanzen in der Praxis sind.

Bernhard Korte, Jens Vygen

Kapitel 22. Standortprobleme

Zusammenfassung

Für Standortprobleme sind sehr unterschiedliche Algorithmen entwickelt worden, die von LP-Rundung bis zu lokaler Suche reichen. In diesem Kapitel werden die wichtigsten Probleme und Approximationsalgorithmen vorgestellt.

Bernhard Korte, Jens Vygen

Backmatter

Titel: Kombinatorische Optimierung
verfasst von: Prof. Dr. Bernhard Korte
Prof. Dr. Jens Vygen
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-57691-5
Print ISBN: 978-3-662-57690-8
DOI: https://doi.org/10.1007/978-3-662-57691-5