Kombinatorische Optimierung: Theorie und Algorithmen

Bernhard Korte, Jens Vygen (auth.)9783540769187, 3540769188

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

---

Table of contents :
Front Matter….Pages I-XIX
Einführung….Pages 1-14
Graphen….Pages 15-54
Lineare Optimierung….Pages 55-77
Algorithmen für lineare Optimierung….Pages 79-107
Ganzzahlige Optimierung….Pages 109-139
Aufspannende Bäume und Arboreszenzen….Pages 141-165
Kürzeste Wege….Pages 167-182
Netzwerkflüsse….Pages 183-218
Flüsse mit minimalen Kosten….Pages 219-248
Maximale Matchings….Pages 249-280
Gewichtete Matchings….Pages 281-308
b -Matchings und T -Joins….Pages 309-328
Matroide….Pages 329-362
Verallgemeinerungen von Matroiden….Pages 363-385
NP -Vollständigkeit….Pages 387-422
Approximationsalgorithmen….Pages 423-471
Das Knapsack-Problem….Pages 473-483
Bin-Packing….Pages 485-502
Mehrgüterflüsse und kantendisjunkte Wege….Pages 503-528
Netzwerk-Design-Probleme….Pages 529-566
Das Traveling-Salesman-Problem….Pages 567-605
Standortprobleme….Pages 607-645
Back Matter….Pages 647-675