An ETH-Tight Exact Algorithm for Euclidean TSP

DOI10.1137/22M1469122MaRDI QIDQ6156029zbMATH OpenOpenAlexFDO

Authors Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay

Publication date 9 June 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.06933

zbMATH Keywords

subexponential algorithmseparator theoremEuclidean traveling salesman

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We study exact algorithms for Euclidean TSP in $mathbb{R}^d$. In the early 1990s algorithms with $n^{O(sqrtn)}$ running time were presented for the planar case, and some years later an algorithm with $n^{O(n^{1-1/d})}$ running time was presented for any $dgeq2$. 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 $2^{O(n^{1-1/d-epsilon})}$ algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a $2^{O(n^{1-1/d})}$ algorithm and by showing that a $2^{o(n^{1-1/d})}$ algorithm does not exist unless ETH fails.

Recommendations

• scientific article; zbMATH DE number 1163704
• Euclidean TSP in narrow strips
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

Cites work

• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• Approximation algorithms for polynomial-expansion and low-density graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Minimum-weight triangulation is NP-hard
• Net and prune: a linear time algorithm for Euclidean distance problems
• On the complexity of \(k\)-SAT
• Open problems around exact algorithms
• Parameterized algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Reducibility among combinatorial problems
• The Euclidean traveling salesman problem is NP-complete
• The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
• The searching over separators strategy to solve some NP-hard problems in subexponential time

Cited in

(4)

• On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances
• Euclidean TSP in narrow strips
• The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
• The homogeneous broadcast problem in narrow and wide strips. I: Algorithms

This page was built for publication: An ETH-Tight Exact Algorithm for Euclidean TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6156029)