Combinatorial Optimization

Theory and Algorithms
4th Auflage Softcover version of original hardcover Auflage 2008
ISBN: 978-3-642-09092-9
Verlag: Springer

Buch, Englisch, Band 21, 627 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 966 g

Reihe: Algorithms and Combinatorics

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.

Zielgruppe

Research

Autoren/Hrsg.

Vygen, Jens

Korte, Bernhard

Fachgebiete

• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

Graphs.- Linear Programming.- Linear Programming Algorithms.- Integer Programming.- Spanning Trees and Arborescences.- Shortest Paths.- Network Flows.- Minimum Cost Flows.- Maximum Matchings.- Weighted Matching.- b-Matchings and T-Joins.- Matroids.- Generalizations of Matroids.- NP-Completeness.- Approximation Algorithms.- The Knapsack Problem.- Bin-Packing.- Multicommodity Flows and Edge-Disjoint Paths.- Network Design Problems.- The Traveling Salesman Problem.- Facility Location.