Overview
- 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 sixth edition
Part of the book series: Algorithms and Combinatorics (AC, volume 21)
Access this book
Tax calculation will be finalised at checkout
Other ways to access
Table of contents (22 chapters)
Keywords
About this book
This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references.
This sixth edition has again been updated, revised, and significantly extended. Among other additions, there are new sections on shallow-light trees, submodular function maximization, smoothed analysis of the knapsack problem, the (ln 4+ɛ)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues torepresent the state of the art of combinatorial optimization.
Authors and Affiliations
About the authors
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.
Bibliographic Information
Book Title: Combinatorial Optimization
Book Subtitle: Theory and Algorithms
Authors: Bernhard Korte, Jens Vygen
Series Title: Algorithms and Combinatorics
DOI: https://doi.org/10.1007/978-3-662-56039-6
Publisher: Springer Berlin, Heidelberg
eBook Packages: Mathematics and Statistics, Mathematics and Statistics (R0)
Copyright Information: Springer-Verlag GmbH Germany, part of Springer Nature 2018
Hardcover ISBN: 978-3-662-56038-9Published: 23 March 2018
Softcover ISBN: 978-3-662-58566-5Published: 11 January 2019
eBook ISBN: 978-3-662-56039-6Published: 13 March 2018
Series ISSN: 0937-5511
Series E-ISSN: 2197-6783
Edition Number: 6
Number of Pages: XXI, 698
Number of Illustrations: 78 b/w illustrations
Topics: Combinatorics, Calculus of Variations and Optimal Control; Optimization, Mathematics of Computing, Operations Research/Decision Theory