Brief Biography
The oldest of four children and son of a junior high school teacher, Richard Manning Karp was born in Boston, Massachusetts. Karp attended Boston Latin School and developed an early interest in mathematics. He attended nearby Harvard University for his undergraduate education but concluded that a career in pure mathematics was not for him. He decided to remain at Harvard and pursue graduate study. Starting in 1955, Karp began working at the university’s computation lab, spending productive summers with the Massachusetts Institute of Technology’s Lincoln Laboratory and General Electric. He wrote his dissertation on the analysis of programs with graph theory algorithms under Anthony G. Oettinger. After receiving his PhD, Karp joined the staff at IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York.
At IBM, Karp was assigned to work on algorithms for logic circuit design. As the field of combinatorial algorithms grew, the company hired Alan Hoffman to head a combinatorics research group. Hoffman became a mentor for Karp whose work was starting to include the design parallel computation models.
Interested in teaching, Karp moved to the University of California, Berkeley in 1968. He saw the move to Berkeley as the end of his “scientific apprenticeship.” As a professor, Karp never set a thesis problem for his students and instead worked closely with each individual to develop a direction that best fit their interests and talents. In 1971, he read a paper by Steve Cook on the proposition satisfiability problem. This inspired Karp to develop the notion of NP-completeness, which successfully placed computational complexity theory in touch with real world applications. In 1972, he and Jack Edmonds devised the Edmonds-Karp algorithm, an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network.
Karp’s algorithmic work has had a significant influence on operations research. His 1977 paper on a probabilistic analysis of portioning algorithms for the travelling-salesman problem was recognized as “the first major application of probabilistic analysis to a combinatorial optimization problem” and was awarded the Frederick W. Lanchester Prize. Karp’s contributions show that traditional combinatorial optimizations problems are equally difficult in the sense that there is an efficient algorithm for solving any single problem if and only if there are efficient algorithms for solving all of them. In 1990, he was awarded the John von Neumann Theory Prize for his seminal developments in computational theory and algorithms in operations research and the management sciences.
In addition to his theory-driven work, Karp has contributed computational molecular biology. Starting in the early 1990s, he began to seriously think about the application of his algorithmic knowledge to biology and medicine. Karp joined University of Washington in 1994 as an Adjunct Professor of Molecular Biology to further explore this subject. He developed an interest in the computational mapping of the human genome. As Karp worked more with real world applications, he began to criticize the theory community for focusing on “artificial problems” and being “ingrown.”
In addition to the Lanchester and von Neumann Prizes, Karp has received a number of additional accolades including the National Medal of Science. In 1985 he won the Alan M. Turing Award, one of the highest honors a computer scientist can receive.
Other Biographies
Wikipedia Entry for Richard M. Karp
Parallel Computing Research Newsletter. Parallel Computer Pioneers - Richard M. Karp. Accessed April 30, 2015. (link)
University of California, Berkeley Electrical Engineering & Computer Sciences. Faculty: Richard M. Karp. Accessed April 30, 2015. (link)
Klarreich, E (2013) Science Lives: Richard Karp. Accessed October 4, 2018 (link)
Education
Harvard University, AB 1955
Harvard University, SM 1956
Harvard University, PhD 1959 (Mathematics Genealogy)
Affiliations
Academic Affiliations
- Harvard University
- Massachusetts Institute of Technology
- University of California, Berkeley
- University of Washington
Non-Academic Affiliations
Key Interests in OR/MS
Methodologies
Application Areas
- Biology/Genomics
Oral Histories
Simons Foundation. Science Lives: Richard Karp. Interviewed by Christos Papadimitriou. Published December 13, 2013. Accessed May 11, 2015. (video)
Memoirs and Autobiographies
Memoirs
Simons Foundation. Science Lives: Richard Karp. Interviewed by Christos Papadimitriou. Published December 13, 2013. Accessed May 11, 2015. (video)
Karp R. M. (1999) The mysteries of algorithms. Calude C. S., ed. in Peoples & Ideas in Theoretical Computer Science, 146-162. Springer: New York. (link)
Awards and Honors
Frederick W. Lanchester Prize 1977
Alan M. Turing Award 1985
John von Neumann Theory Prize 1990
National Academy of Engineering 1992
Association of Computing Machinery Fellow 1994
National Medal of Science 1996
Institute for Operations Research and the Management Sciences Fellow 2002
Selected Publications
Karp R. M. & Held M. (1962) A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1): 196-210.
Karp R. M. & Millter R. E. (1969) Parallel program schemata. Journal of Computer and System Sciences, 3(2): 147-195.
Karp R. M. (1970) The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6): 1138-1162.
Edmonds J. & Karp R. M. (1972) Theoretical improvement in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery, 19(2): 248-264.
Karp R. M. (1972) Reducibility Among Combinatorial Problems. Miller R. E. & Thatcher J. W., eds. inComplexity of Computer Computations, 85-103. Plenum: New York.
Hopcroft J. E. & Karp R. M. (1973) An n^5/2 algorithm for maximum matching in bipartite graphs. SIAM Journal on Computing, 2(4): 225-231.
Karp R. M. (1977) A Probabilistic Analysis of Partitioning Algorithms for the Travelling-Salesman Problem in the Plane. Mathematics of Operations Research, 2(3): 209-224.
Karp R. M. & Rabin M. O. (1987) Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2): 249-260.
Karp R. M. & Vijaya R. (1988) A Survey of Parallel Algorithms for Shared-Memory Machines. EECS Department University of California, Berkeley: Berkeley, CA.
Fiat A., Karp R. M., Luby M., McGeoch L. A., Sleator D. D., & Young N. E. (1991) Competitive paging algorithms. Journal of Algorithms, 12(4): 685-699.
Jordan M. I., Karp R. M., & Xing E. P. (2001) Feature selection for high-dimensional genomic microarray data. ICML, 1: 601-608.