zbMATH — the first resource for mathematics

Combinatorial optimization: algorithms and complexity. Corr. repr. of the 1982 original. (English) Zbl 0944.90066
Mineola, NY: Dover Publications, Inc. xvi, 496 p. (1998).
The first part of this textbook provides an introduction to linear programming and duality theory. The second part concentrates on graph applications such as flow, matching, and spanning tree problems. The last part covers integer linear programming and NP-completeness and provides practical ways to deal with intractable problems. Each chapter is supplemented by exercises.
The authors decided to republish the 1982 edition (see Zbl 0503.90060) (with errors corrected) as a piece of documentation of the development of the research in the area.
For more recent overviews the authors refer to: A. Schrijver, Theory of linear and integer programming, New York: Wiley-Interscience (1986; Zbl 0665.90063), (1998; Zbl 0970.90052); R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network flows. Englewood Cliffs, NJ: Prentice-Hall (1993; Zbl 1201.90001); C. H. Papadimitriou, Computational complexity, Addison-Wesley (1994; Zbl 0833.68049); D. Hochbaum et al. (eds.), Approximation Algorithms for NP-hard problems, PWS Publishing (1997); C. R. Reeves (ed.), Modern heuristic techniques for combinatorial problems. New York, NY: Halstead Press (Wiley) (1993; Zbl 0942.90500).

90C27 Combinatorial optimization
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C05 Linear programming
90C46 Optimality conditions and duality in mathematical programming
90C35 Programming involving graphs or networks
90C10 Integer programming
90B10 Deterministic network models in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity