Korte / Vygen Kombinatorische Optimierung

Theorie und Algorithmen
2008
ISBN: 978-3-540-76919-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 675 Seiten, eBook

Reihe: Masterclass

Dieses umfassende Lehrbuch über kombinatorische Optimierung ist die deutsche Übersetzung der vierten, wesentlich erweiterten Auflage des Buches „Combinatorial Optimization – Theory and Algorithms", dessen erste Auflage im Jahr 2000 erschienen ist. Es ist aus verschiedenen Vorlesungen über kombinatorische Optimierung und Spezialvorlesungen für Fortgeschrittene hervorgegangen, die die Autoren an der Universität Bonn gehalten haben. Das Buch enthält vornehmlich theoretische Resultate und detaillierte Algorithmen mit beweisbar guten Laufzeiten und Ergebnissen, aber keine Heuristiken. Es werden vollständige Beweise, auch für viele tiefe und neue Resultate gegeben, von denen einige bisher in der Lehrbuchliteratur noch nicht erschienen sind. Ferner enthält das Buch viele Übungsaufgaben und ein umfassendes Literaturverzeichnis. Es 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

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Korte, Bernhard

Vygen, Jens

Weitere Mitwirkende

Randow, Rabe

Inhaltsverzeichnis

Einführung.- Graphen.- Lineare Optimierung.- Algorithmen für lineare Optimierung.- Ganzzahlige Optimierung.- Aufspannende Bäume und Arboreszenzen.- Kürzeste Wege.- Netzwerkflüsse.- Flüsse mit minimalen Kosten.- Maximale Matchings.- Gewichtete Matchings.- b-Matchings und T-Joins.- Matroide.- Verallgemeinerungen von Matroiden.- NP-Vollständigkeit.- Approximationsalgorithmen.- Das Knapsack-Problem.- Bin-Packing.- Mehrgüterflüsse und kantendisjunkte Wege.- Netzwerk-Design-Probleme.- Das Traveling-Salesman-Problem.- Standortprobleme.