Joe Mitchell wins Goedel Prize Award |
 |
Go Back to News Highlights |
Headlines
The Goedel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the ACM SIGACT. This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and ACM Symposium on the Theory of Computing (STOC).
Details
The Goedel Prize 2010 is awarded to Sanjeev Arora and Joe Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP):
Joe Mitchell (1999). Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM J. Computing 28(4), 1298-1309.
S. Arora. (1998). Polynomial-time approximation schemes for Euclidean TSP and other geometric problems, Journal ACM 45(5), 753-782.
The Euclidean Travelling Salesman Problem in dimension 2 is one of those old, seemingly innocent problems known to be NP hard, but still not known to be in NP. At the time of the publication, the impact of the Euclidean assumption was hardly understood: the best polynomial-time approximation scheme could only guarantee 50% error at best.
Arora and Mitchell showed that solutions which are arbitrarily close to optimal in a relative sense can be found in polynomial time. These techniques, further simplified, improved and then generalized, occupy a chapter of their own in the theory of approximation algorithms.
The discovery of a PTAS for ETSP, with its long trail of consequences, counts as a crowning achievement of geometric optimization.
The Award Committe:- Cynthia Dwork, Microsoft
- Johan Hastad, KTH Stockholm
- Jean-Pierre Jouannaud, INRIA and Tsinghua University, chair
- Mogens Nielsen, Aarhus University
- Mike Paterson, University of Warwick
- Eli Upfal, Brown University