zbMATH — the first resource for mathematics

Reducibility among combinatorial problems. (English) Zbl 1187.90014
J√ľnger, Michael (ed.) et al., 50 years of integer programming 1958–2008. From the early years to the state-of-the-art. Papers based on the presentations at the special session at the 12th combinatorial optimization workshop AUSSOIS 2008, Aussois, France January 7–11, 2008. With DVD. Berlin: Springer (ISBN 978-3-540-68274-5/hbk; 978-3-540-68279-0/ebook). 219-241 (2010).
From the introduction: “Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held. These experiences made me aware that seemingly simple discrete optimization problems could hold the seeds of combinatorial explosions. The work of Dantzig, Fulkerson, Hoffman, Edmonds, Lawler and other pioneers on network flows, matching and matroids acquainted me with the elegant and efficient algorithms that were sometimes possible. Jack Edmonds’ papers and a few key discussions with him drew my attention to the crucial distinction between polynomial-time and superpolynomial-time solvability. I was also influenced by Jack’s emphasis on min-max theorems as a tool for fast verification of optimal solutions, which foreshadowed Steve Cook’s definition of the complexity class NP. Another influence was George Dantzig’s suggestion that integer programming could serve as a universal format for combinatorial optimization problems.”
Includes reprint of [R. M. Karp, “Reducibility among combinatorial problems”, in: Complexity of computer computations. Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, New York, 1972. New York: Plenum Press. 85–103 (1972)]; for a Russian translation see [Kibern. Sb., Nov. Ser. 12, 16–83 (1975; Zbl 0366.68041)].
For the entire collection see [Zbl 1181.90003].

90-03 History of operations research and mathematical programming
90C27 Combinatorial optimization
01A75 Collected or selected works; reprintings or translations of classics
Full Text: DOI