Papadimitriou, Christos H.; Steiglitz, Kenneth 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). Reviewer: H.-C.Wirth (Würzburg) Cited in 258 Documents MSC: 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 Keywords:optimization; primal-dual algorithm; flow; spanning tree; approximation algorithm; branch-and-bound algorithm; integer linear programming; NP-completeness Citations:Zbl 0503.90060; Zbl 0665.90063; Zbl 0970.90052; Zbl 1201.90001; Zbl 0833.68049; Zbl 0942.90500 PDFBibTeX XMLCite \textit{C. H. Papadimitriou} and \textit{K. Steiglitz}, Combinatorial optimization: algorithms and complexity. Corr. repr. of the 1982 original. Mineola, NY: Dover Publications, Inc. (1998; Zbl 0944.90066)