## Abstract

We study exact algorithms for E UCLIDEAN TSP in ℝ
^{d}
. In the early 1990s algorithms with n
^{O(√n)}
running time were presented for the planar case, and some years later an algorithm with n
^{O(n1-1/d)}
running time was presented for any d ≧ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on EUCLIDEAN TSP, except for a lower bound stating that the problem admits no 2O(n
^{1-1/d-ϵ}
) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of E UCLIDEAN TSP by giving a 2
^{O(n-1/d)}
algorithm and by showing that a 2
^{o(n1-1/d}
) algorithm does not exist unless ETH fails.

Original language | English |
---|---|

Title of host publication | Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |

Editors | Mikkel Thorup |

Place of Publication | Piscataway |

Publisher | IEEE Computer Society |

Pages | 450-461 |

Number of pages | 12 |

ISBN (Electronic) | 978-1-5386-4230-6 |

DOIs | |

Publication status | Published - 30 Nov 2018 |

Event | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France Duration: 7 Oct 2018 → 9 Oct 2018 |

### Conference

Conference | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
---|---|

Country | France |

City | Paris |

Period | 7/10/18 → 9/10/18 |

## Keywords

- ETH
- Euclidean TSP
- Separator theorem
- Subexponential algorithms
- separator theorem