Richard M. Karp

Born:
January 3, 1935

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
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

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

Dickson Prize in Science 2008

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.