An ETH-Tight Exact Algorithm for Euclidean TSP

DOI10.1137/22M1469122arXiv1807.06933OpenAlexW2951388475MaRDI QIDQ6156029FDOQ6156029

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)

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.

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

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

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)

Cites Work

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

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)