### 2010 Gödel Prize

The 2010 Gödel Prize is awarded to Sanjeev Arora and Joseph S.B.
Mitchell for their concurrent discovery of a polynomial-time
approximation scheme (PTAS) for the Euclidean Travelling Salesman
Problem (ETSP):

Sanjeev Arora. (1998). Polynomial-time approximation schemes for
Euclidean TSP and other geometric problems, Journal ACM 45(5),
753-782.

Joseph S.B. 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.

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.

#### Award Committee

- Cynthia Dwork (Microsoft)
- Johan Håstad (KTH Stockholm)
- Jean-Pierre Jouannaud (INRIA and Tsinghua University), chair
- Mogens Nielsen (Aarhus University)
- Mike Paterson (University of Warwick)
- Eli Upfal (Brown University)