zbMATH — the first resource for mathematics

Combinatorial optimization. Theory and algorithms. (English) Zbl 0953.90052
Algorithms and Combinatorics. 21. Berlin: Springer. xi, 530 p. (2000).
This book describes the most important ideas, theoretical results, algorithms in combinatorial optimization and covers an advanced graduate text which can also be used as an up-to-date reference work for current research. It starts by reviewing basic graph theory and proving those results in (integer) linear programming which are most relevant for combinatorial optimization. The book is organized into twenty chapters as follows: 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.
Chapters 5-13 have polynomial-time algorithms, while most of the problems studied in chapters 14-20 are NP-hard, i.e. a polynomial-time algorithm is unlikely to exist.
All results are accompanied by detailed proofs. At the end of each chapter there are a number of exercises containing additional results and applications of the material in that chapter. Each chapter ends with a list of references, incuding texts recommended for further study.

90C27 Combinatorial optimization
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research