When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree

DOI10.1137/S0097539799352735zbMath0963.68080MaRDI QIDQ4507360

Luca Trevisan

Publication date: 18 October 2000

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

zbMATH Keywords

computational complexitycombinatorial optimizationSteiner tree problemtraveling salesman problemhardness of approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items (9)

Faster algorithms for orienteering and \(k\)-TSP ⋮ Optimizing Read Reversals for Sequence Compression ⋮ Approximate Euclidean Steiner trees ⋮ A Modern View on Stability of Approximation ⋮ Scheduling on a graph with release times ⋮ New Approximation Algorithms for (1,2)-TSP ⋮ TSP with bounded metrics ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Travelling on graphs with small highway dimension

This page was built for publication: When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree