Gap-ETH-tight approximation scheme for Euclidean TSP

In this talk, we will see an elegant modification to Arora's scheme called "sparsity-sensitive patching", which fine-tunes the granularity with which the tour is simplified. The resulting algorithm has running time 2^O(epsilon^(1-d)) n log n for any fixed d, which is faster than Arora's scheme, and also faster than the approximation scheme of Rao and Smith. In fact, the epsilon-dependence of our algorithm is optimal under the Gap Exponential Time Hypothesis.

The talk is based on joint work with Jesper Nederlof and Karol Wegrzycki. A preprint is available at https://arxiv.org/abs/2011.03778

--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.