Difference between revisions of "Richard Karp"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 22: | Line 22: | ||
* [[Richard Karp]], [https://dblp.uni-trier.de/pers/hd/m/Miller:Raymond_E= Raymond E. Miller] ('''1969'''). ''Parallel Program Schemata''. [https://en.wikipedia.org/wiki/Journal_of_Computer_and_System_Sciences Journal of Computer and System Sciences], Vol. 3, No. 2, [https://core.ac.uk/download/pdf/82202840.pdf pdf] | * [[Richard Karp]], [https://dblp.uni-trier.de/pers/hd/m/Miller:Raymond_E= Raymond E. Miller] ('''1969'''). ''Parallel Program Schemata''. [https://en.wikipedia.org/wiki/Journal_of_Computer_and_System_Sciences Journal of Computer and System Sciences], Vol. 3, No. 2, [https://core.ac.uk/download/pdf/82202840.pdf pdf] | ||
==1970 ...== | ==1970 ...== | ||
− | * [https://dblp.uni-trier.de/pers/hd/h/Held:Michael Michael Held], [[Richard Karp]] ('''1970'''). ''The Traveling-Salesman Problem and Minimum Spanning Trees''. [https://en.wikipedia.org/wiki/Operations_Research_(journal) Operations Research], Vol. 18, No. 6, [https://www.cse.wustl.edu/~ychen/7102/Karp-TSP.pdf pdf] | + | * [https://dblp.uni-trier.de/pers/hd/h/Held:Michael Michael Held], [[Richard Karp]] ('''1970'''). ''The Traveling-Salesman Problem and Minimum Spanning Trees''. [https://en.wikipedia.org/wiki/Operations_Research_(journal) Operations Research], Vol. 18, No. 6, [https://www.cse.wustl.edu/~ychen/7102/Karp-TSP.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling salesman problem from Wikipedia]</ref> |
* [https://dblp.uni-trier.de/pers/hd/h/Held:Michael Michael Held], [[Richard Karp]] ('''1971'''). ''[https://link.springer.com/article/10.1007%2FBF01584070 The traveling-salesman problem and minimum spanning trees: Part II'']. [https://en.wikipedia.org/wiki/Mathematical_Programming Mathematical Programming], Vol. 1, No. 1 | * [https://dblp.uni-trier.de/pers/hd/h/Held:Michael Michael Held], [[Richard Karp]] ('''1971'''). ''[https://link.springer.com/article/10.1007%2FBF01584070 The traveling-salesman problem and minimum spanning trees: Part II'']. [https://en.wikipedia.org/wiki/Mathematical_Programming Mathematical Programming], Vol. 1, No. 1 | ||
* [[Richard Karp]], [https://dblp.uni-trier.de/pers/hd/m/Miller:Raymond_E= Raymond E. Miller], [[Mathematician#ALRosenberg|Arnold L. Rosenberg]] ('''1972'''). ''[https://www.semanticscholar.org/paper/Rapid-Identification-of-Repeated-Patterns-in-Trees-Karp-Miller/b3387ef7e1466b91174604e097a6bd6fa57498d2 Rapid Identification of Repeated Patterns in Strings, Trees and Arrays]''. [https://dblp.uni-trier.de/db/conf/stoc/stoc72.html STOC 1972] | * [[Richard Karp]], [https://dblp.uni-trier.de/pers/hd/m/Miller:Raymond_E= Raymond E. Miller], [[Mathematician#ALRosenberg|Arnold L. Rosenberg]] ('''1972'''). ''[https://www.semanticscholar.org/paper/Rapid-Identification-of-Repeated-Patterns-in-Trees-Karp-Miller/b3387ef7e1466b91174604e097a6bd6fa57498d2 Rapid Identification of Repeated Patterns in Strings, Trees and Arrays]''. [https://dblp.uni-trier.de/db/conf/stoc/stoc72.html STOC 1972] | ||
Line 45: | Line 45: | ||
==2010 ...== | ==2010 ...== | ||
* [[Richard Karp]] ('''2010'''). ''Reducibility Among Combinatorial Problems''. [https://dblp.uni-trier.de/db/books/daglib/0023873.html 50 Years of Integer Programming] | * [[Richard Karp]] ('''2010'''). ''Reducibility Among Combinatorial Problems''. [https://dblp.uni-trier.de/db/books/daglib/0023873.html 50 Years of Integer Programming] | ||
+ | * [[Mathematician#KChandrasekaran|Karthekeyan Chandrasekaran]], [[Richard Karp]] ('''2012'''). ''Finding a most biased coin with fewest flips''. [https://arxiv.org/abs/1202.3639 arXiv:1202.3639] | ||
+ | * [[Mathematician#CHPapadimitriou|Christos H. Papadimitriou]], [[Mathematician#LAdleman|Leonard Adleman]], [[Richard Karp]], [[Donald Knuth]], [[Mathematician#RETarjan|Robert E. Tarjan]], [[Mathematician#LValiant|Leslie Valiant]] ('''2012'''). ''[https://dl.acm.org/citation.cfm?id=2322189 An Algorithmic View of the Universe]''. [[Algorithms#ACM-Turing|ACM-Turing 2012]] | ||
+ | * [[Mathematician#IAdler|Ilan Adler]], [[Mathematician#YangCao|Yang Cao]], [[Richard Karp]], [[Mathematician#EAPekoz|Erol A. Peköz]], [[Mathematician#SMRoss|Sheldon M. Ross]] ('''2017'''). ''[https://pubsonline.informs.org/doi/10.1287/opre.2017.1657 Random Knockout Tournaments]''. [https://en.wikipedia.org/wiki/Operations_Research_(journal) Operations Research], Vol. 65, No. 6, [https://arxiv.org/abs/1612.04448 arXiv:1612.04448] | ||
=External Links= | =External Links= |
Latest revision as of 12:46, 21 November 2018
Richard M. Karp,
an American mathematician, computer scientist and pioneer in theoretical computer science and computational complexity for which he received a Turing Award in 1985, the Harvey Prize in 1998, the Benjamin Franklin Medal in 2004, and the Kyoto Prize in 2008 [2] and several honorary degrees.
Richard Karp is professor emeritus at Department of Electrical Engineering and Computer Sciences with additional appointments in mathematics, bioengineering and operations research, University of California, Berkeley.
His research interests further include combinatorial algorithms, discrete probability, computational biology, and internet algorithms.
Karp introduced the now standard methodology for proving problems to be NP-complete. He is known for Karp's 21 NP-complete problems, the Edmonds–Karp algorithm, the Hopcroft–Karp algorithm, the Karp–Lipton theorem, and the Rabin–Karp algorithm.
Contents
StarTech
According to primary StarTech author Bradley Kuszmaul, Hans Berliner, Richard Karp, David Slate, and Lewis Stiller contributed to a mini-seminar on computer chess held at Thinking Machines Corporation on August 12, 1991. In particular, Richard Karp suggested that StarTech should be based on Berliner’s serial program HiTech rather than GNU Chess [3] .
Selected Publications
1959
- Richard Karp (1959). Some Applications of Logical Syntax to Digital Computer Programming. Ph.D. thesis, Harvard University
1960 ...
- Richard Karp (1960). A Note on the Applicaton of Graph Theory to Digital Computer Programming. Information and Control, Vol. 3, No. 2, pdf
- Richard Karp (1964). Some Techniques of State Assignment for Synchronous Sequential Machines. IEEE Transactions on Electronic Computers, Vol. 13, No. 5
- Richard Karp (1967). Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines. Journal of the ACM, Vol. 14, No. 3
- Richard Karp, Raymond E. Miller (1969). Parallel Program Schemata. Journal of Computer and System Sciences, Vol. 3, No. 2, pdf
1970 ...
- Michael Held, Richard Karp (1970). The Traveling-Salesman Problem and Minimum Spanning Trees. Operations Research, Vol. 18, No. 6, pdf [5]
- Michael Held, Richard Karp (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, Vol. 1, No. 1
- Richard Karp, Raymond E. Miller, Arnold L. Rosenberg (1972). Rapid Identification of Repeated Patterns in Strings, Trees and Arrays. STOC 1972
- Richard Karp (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations 1972, pdf
- Richard Karp (1977). Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane. Mathematics of Operations Research, Vol. 2, No. 3
1980 ...
- Manuel Blum, Richard Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis (1981). The Complexity of Testing Whether a Graph is a Superconcentrator. Information Processing Letters, Vol. 13, Nos. 4/5
- Richard Karp (1986). Combinatorics, complexity, and randomness. Communications of the ACM, Vol. 29, No. 2
- Richard Karp, Yanjun Zhang (1988). A randomized parallel branch-and-bound procedure. STOC '88
- Richard Karp, Yanjun Zhang (1989). On parallel evaluation of game trees. SPAA '89
1990 ...
- Richard Karp, Yanjun Zhang (1993). Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, Vol. 40, No. 3
- Richard Karp, Yanjun Zhang (1995). Bounded branching process and and/or tree evaluation. Random Structures & Algorithms, Vol. 7, No. 2
- Richard Karp, Yanjun Zhang (1998). On Parallel Evaluation of Game Trees. Journal of the ACM, Vol. 45, No. 6
2000 ...
- Richard Karp (2000). The Genomics Revolution and Its Challenges for Algorithmic Research. ICALP 2000
- Aditya Akella, Srinivasan Seshan, Richard Karp, Scott Shenker, Christos H. Papadimitriou (2002). Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. SIGCOMM 2002
- Richard Karp, Claire Kenyon (2003). A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. RANDOM-APPROX 2003
- Richard Karp (2008). Computer Science as a Lens on the Sciences. ICDCS 2008
- Richard Karp (2008). George Dantzig's impact on the theory of computation. Discrete Optimization, Vol 5, No. 2
- P. Brighten Godfrey, Richard Karp (2009). On the Price of Heterogeneity in Parallel Systems. Theory of Computing Systems, Vol. 45, No. 2
2010 ...
- Richard Karp (2010). Reducibility Among Combinatorial Problems. 50 Years of Integer Programming
- Karthekeyan Chandrasekaran, Richard Karp (2012). Finding a most biased coin with fewest flips. arXiv:1202.3639
- Christos H. Papadimitriou, Leonard Adleman, Richard Karp, Donald Knuth, Robert E. Tarjan, Leslie Valiant (2012). An Algorithmic View of the Universe. ACM-Turing 2012
- Ilan Adler, Yang Cao, Richard Karp, Erol A. Peköz, Sheldon M. Ross (2017). Random Knockout Tournaments. Operations Research, Vol. 65, No. 6, arXiv:1612.04448
External Links
- Richard M. Karp's Home Page
- Richard M. Karp from Wikipedia
- Richard M. Karp | EECS at UC Berkeley
- The Mathematics Genealogy Project - Richard Karp
- Details for Richard Karp - Oberwolfach Photo Collection
- Message from Richard Manning Karp - The 2008 Kyoto Prize, YouTube Video
References
- ↑ Richard Karp giving a talk at the EPFL on 13th of July 2009, Category:Richard Karp - Wikimedia Commons
- ↑ Richard M. Karp from Wikipedia
- ↑ Bradley C. Kuszmaul (1994). Synchronized MIMD Computing. Ph. D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, pdf, pp. 146, Acknowledgments
- ↑ dblp: Richard M. Karp
- ↑ Travelling salesman problem from Wikipedia