Richard M. Karp

Nach der Boston Latin School besuchte er die Harvard University, wo er 1955 seinen Bachelor in Mathematik, 1956 seinen Master in Mathematik und 1959 seinen Ph.D. in Angewandter Mathematik erwarb. Anschließend arbeitete er bis 1968 im IBM Thomas J. Watson Research Center. Daneben war er 1962 auf Teilzeitbasis wissenschaftlicher Assistent an der New York University, 1964 bis 1965 außerordentlicher Gastprofessor für Elektrotechnik an der University of Michigan, 1965 bis 1968 außerordentlicher Gastprofessor und ordentlicher Gastprofessor für Elektrotechnik am Polytechnic Institute of Brooklyn (in Teilzeit) und 1967 bis 1968 außerordentlicher Professor für Industrial Engineering und Management Engineering an der Columbia University (in Teilzeit). 1968 wurde er Professor für Informatik, Mathematik und Operations Research an der University of California, Berkeley. Von einer vierjährigen Periode als Professor an der University of Washington (1995 bis 1999 als Professor für Informatik und Lehrbeauftragter für molekulare Biotechnologie) abgesehen, blieb er seither in Berkeley, wo er neben der Universität auch am International Computer Science Institute und zeitweise auch am Mathematical Sciences Research Institute tätig ist bzw. war.

Karp gehört oder gehörte dem redaktionellen Beirat zahlreicher Zeitschriften an, darunter das Journal of Computer and System Sciences und die Proceedings of the National Academy of Sciences, an. Daneben war er im Fachbeirat des Max-Planck-Instituts für Informatik und beriet IBM Research, Hewlett-Packard, die Computer Professionals for Social Responsibility, das International Institute for Applied Systems Analysis und das Center for Discrete Mathematics and Theoretical Computer Science. Er war im Aufsichtsrat des Weizmann-Instituts für Wissenschaften und des Institute for Mathematics and its Applications sowie im Vorstand des Miller Institute for Basic Research in Science und leitete u. a. die Computer Science Planning Group des National Research Council und die Sektion Computer and Information Sciences der National Academy of Sciences.

1971 entwickelte Karp mit Jack Edmonds den Edmonds-Karp-Algorithmus zur Lösung des Max-Flow-Problems in Netzwerken. 1972 veröffentlichte er einen Artikel, in dem er die NP-Vollständigkeit einer Reihe von graphentheoretischen Problemen nachwies, darunter das Hamiltonkreisproblem, das Cliquenproblem und das Rucksackproblem. Diese wurden bekannt als Karps 21 NP-vollständige Probleme. 1973 entwickelte er mit John E. Hopcroft den Algorithmus von Hopcroft und Karp zur Bestimmung einer größten Paarung in bipartiten Graphen. 1987 entwickelte er gemeinsam mit Michael O. Rabin den Rabin-Karp-Algorithmus zur String-Suche. Zu seinen Forschungsschwerpunkten gehören kombinatorische und parallele Algorithmen, Bioinformatik und Netzwerke.

Zu Karps rund 40 Doktoranden gehören Narendra Karmarkar (Fulkerson-Preis 1988), Phillip Gibbons (Paris-Kanellakis-Preis 2019) und Rajeev Motwani (Gödel-Preis 2001).

• 1977: Frederick-W.-Lanchester-Preis (mit Gérard Cornuéjols, Marshall Fisher und George Nemhauser)Frederick-W.-Lanchester-Preis^[1]
• 1979: Fulkerson-Preis
• 1980: Mitglied der National Academy of Sciences und der New York Academy of Sciences
• 1983: Invited Speaker auf dem Internationalen Mathematikerkongress in Warschau (The probabilistic analysis of combinatorial algorithms).
• 1985: Turing Award und Mitglied der American Academy of Arts and Sciences
• 1986: Ehrendoktortitel der University of Pennsylvania
• 1989: Ehrendoktortitel des Technion
• 1990: John-von-Neumann-Theorie-Preis, Ehrendoktortitel der University of Massachusetts und Gründungs-Fellow des Institute of Combinatorics and its Applications
• 1991: Fellow der American Association for the Advancement of Science
• 1992: Mitglied der National Academy of Engineering und Ehrendoktortitel der Georgetown University
• 1994: Mitglied der American Philosophical Society und Fellow der ACM
• 1996: National Medal of Science
• 1997: Harvard Centennial Medal
• 1998: Harvey-Preis
• 2000: EATCS-Award
• 2001: Ehrendoktortitel der University of Central Florida
• 2002: Auslandsmitglied der Académie des sciences, Ehrendoktortitel der Carleton University^[2] und Fellow des Institute for Operations Research and the Management Sciences
• 2003: Ehrendoktortitel der ETH Zürich
• 2004: Benjamin-Franklin-Medaille für Informatik und Kognitionswissenschaft, sowie Ehrendoktortitel des Weizmann-Instituts für Wissenschaften und Mitglied der European Academy of Sciences
• 2008: Kyoto-Preis
• 2008: Dickson Prize in Science

• Reducibility Among Combinatorial Problems (PDF; 10,9 MB). In: R. E. Miller, J. W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York 1972, S. 85–103.

• Literatur von und über Richard M. Karp im Katalog der Deutschen Nationalbibliothek
• Interview und Biografie (Memento vom 18. Juni 2008 im Internet Archive) (englisch)
• Website (englisch)

1. ↑ Frederick W. Lanchester Prize. informs.org (Institute for Operations Research and the Management Sciences), archiviert vom Original am 2. Oktober 2015; abgerufen am 16. Februar 2016 (englisch). 
2. ↑ Honorary Degrees Awarded Since 1954 - Senate. carleton.ca, abgerufen am 12. März 2015.