This comprehensive textbook on combinatorial optimization emphasizes theoretical results and algorithms with provably good performance, in contrast to heuristics. The text contains complete but concise proofs, and also provides numerous exercises and references.

Well-written, popular textbook on combinatorial optimization

One of very few textbooks on this topic

Subject area has manifold applications

Offers complete but concise proofs, making it an invaluable practical tool for students

Updated fifth edition

Autorentext

Bernhard Korte is professor of operations research and director of the Research Institute for Discrete Mathematics at the University of Bonn. He founded the Arithmeum in Bonn and received numerous awards, including a honorary doctoral degree and the "Staatspreis NRW". His research interests include combinatorial optimization and chip design.

Jens Vygen is professor of discrete mathematics at the University of Bonn and principal investigator of the Hausdorff Center for Mathematics. He also co-authored the textbook Algorithmic Mathematics and has served as editor of several books and journals. His research interests include combinatorial optimization and algorithms for chip design.

Klappentext
Well-written, popular textbook on combinatorial optimization One of very few textbooks on this topic Subject area has manifold applications Offers complete but concise proofs, making it an invaluable practical tool for students Updated fifth edition

Zusammenfassung

Well-written, popular textbook on combinatorial optimization

One of very few textbooks on this topic

Subject area has manifold applications

Offers complete but concise proofs, making it an invaluable practical tool for students

Updated fifth edition

Inhalt

1 Introduction.- 2 Graphs.- 3 Linear Programming.- 4 Linear Programming Algorithms.- 5 Integer Programming.- 6 Spanning Trees and Arborescences.- 7 Shortest Paths.- 8 Network Flows.- 9 Minimum Cost Flows.- 10 Maximum Matchings.- 11 Weighted Matching.- 12 b -Matchings and T -Joins.- 13 Matroids.- 14 Generalizations of Matroids.- 15 NP -Completeness.- 16 Approximation Algorithms.- 17 The Knapsack Problem.- 18 Bin-Packing.- 19 Multicommodity Flows and Edge-Disjoint Paths.- 20 Network Design Problems.- 21 The Traveling Salesman Problem.- 22 Facility Location.- Indices.