Fine-grained complexity analysis of two classic TSP variants

DOI10.4230/LIPIcs.ICALP.2016.5zbMath1388.68139arXiv1607.02725OpenAlexW3139453558MaRDI QIDQ4598137

Gerhard J. Woeginger, Kevin Buchin, Bart M. P. Jansen, Mark T. de Berg

Publication date: 19 December 2017

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

zbMATH Keywords

traveling salesman problem\(k\)-OPTfine-grained complexitybitonic tours

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (9)

Finding the largest triangle in a graph in expected quadratic time ⋮ On the complexity of restoring corrupted colorings ⋮ Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1] ⋮ Unnamed Item ⋮ The temporal explorer who returns to the base ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions.

This page was built for publication: Fine-grained complexity analysis of two classic TSP variants