Combinatorial Optimization: Theory and Algorithms

✍ Scribed by Bernhard Korte, Jens Vygen (auth.)

• Publisher: Springer Berlin Heidelberg
• Year: 2008
• Tongue: English
• Leaves: 646
• Series: Algorithms and Combinatorics 21
• Edition: 4th
• Category: Library

✦ Synopsis

Now fully updated in a third edition, this is a comprehensive textbook on combinatorial optimization. It puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. The book contains complete but concise proofs, also for many deep results, some of which have not appeared in print before. Recent topics are covered as well, and numerous references are provided. This third edition contains a new chapter on facility location problems, an area which has been extremely active in the past few years. Furthermore there are several new sections and further material on various topics. New exercises and updates in the bibliography were added.

✦ Table of Contents

Front Matter....Pages I-XVII
Introduction....Pages 1-12
Graphs....Pages 13-47
Linear Programming....Pages 49-69
Linear Programming Algorithms....Pages 71-97
Integer Programming....Pages 99-126
Spanning Trees and Arborescences....Pages 127-149
Shortest Paths....Pages 151-164
Network Flows....Pages 165-197
Minimum Cost Flows....Pages 199-226
Maximum Matchings....Pages 227-256
Weighted Matching....Pages 257-283
b -Matchings and T -Joins....Pages 285-303
Matroids....Pages 305-336
Generalizations of Matroids....Pages 337-357
NP -Completeness....Pages 359-392
Approximation Algorithms....Pages 393-437
The Knapsack Problem....Pages 439-448
Bin-Packing....Pages 449-465
Multicommodity Flows and Edge-Disjoint Paths....Pages 467-489
Network Design Problems....Pages 491-525
The Traveling Salesman Problem....Pages 527-562
Facility Location....Pages 563-598
Back Matter....Pages 599-627

✦ Subjects

Combinatorics; Calculus of Variations and Optimal Control; Optimization; Mathematics of Computing