{"id":1075,"date":"2010-03-02T21:23:52","date_gmt":"2010-03-03T01:23:52","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1075"},"modified":"2010-03-02T21:23:52","modified_gmt":"2010-03-03T01:23:52","slug":"david-johnson-to-receive-knuth-prize","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/03\/02\/david-johnson-to-receive-knuth-prize\/","title":{"rendered":"David Johnson to Receive Knuth Prize"},"content":{"rendered":"

\"\"AT&T Labs researcher David Johnson<\/a> will receive this year’s Knuth Prize from the ACM “for his contributions to theoretical and experimental analysis of algorithms”.\u00a0 While Johnson is best known for his NP-Completeness book with Michael Garey, he has had an extraordinarily influential career in both the theory of approximation algorithms and in research on experimental evaluation of algorithms.\u00a0 From the announcement<\/a>:<\/p>\n

The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT<\/a>) will present its 2009 Knuth Prize to David S. Johnson of AT&T Labs for his contributions to theoretical and experimental analysis of algorithms.\u00a0 Johnson\u2019s innovations helped lay the foundation for algorithms used to address optimization problems, which involve the process of finding the best solution from all feasible solutions.\u00a0 In addition, Johnson made many contributions to the early development of NP-completeness theory, which helps identify those problems that are hard to solve efficiently. The Knuth Prize, named in honor of Donald Knuth of Stanford University who has been called the “father” of the analysis of algorithms, will be presented at the ACM Symposium on Theory of Computing (STOC<\/a>) June 6-8, 2010, in Cambridge, MA, where Johnson will present the Knuth Prize Lecture.<\/p><\/blockquote>\n

I got to know David almost 20 years ago when I agreed to coordinate one of his DIMACS Implementation Challenges<\/a>.\u00a0 This cooperation resulted in a book<\/a> and, a decade later, a special issue of Discrete Applied Mathematics<\/em> (with Anuj Mehortra). These Challenges are one of the ways David has explored issues in the evaluation of algorithms.\u00a0 I had the chance recently to give a presentation on the effect of those Challenges<\/a>.\u00a0 David has had an enormous influence on me as I think about how to provide a firmer underpinning to the experimental analysis of algorithms and the way individuals and a field report on results.\u00a0 This Prize makes me wish I had more time to spend on completing a planned system for reporting and confirming computational results<\/a>.<\/p>\n

I guess I am only surprised that David hadn’t already won this prize!\u00a0 Very well deserved.<\/p>\n","protected":false},"excerpt":{"rendered":"

AT&T Labs researcher David Johnson will receive this year’s Knuth Prize from the ACM “for his contributions to theoretical and experimental analysis of algorithms”.\u00a0 While Johnson is best known for his NP-Completeness book with Michael Garey, he has had an extraordinarily influential career in both the theory of approximation algorithms and in research on experimental … Continue reading “David Johnson to Receive Knuth Prize”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[40,44],"tags":[],"class_list":["post-1075","post","type-post","status-publish","format-standard","hentry","category-people","category-prizes"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1075","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1075"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1075\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1075"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1075"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1075"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}