On the approximability of the traveling salesman problem (extended abstract)

DOI10.1145/335305.335320zbMath1296.68083OpenAlexW2076386251MaRDI QIDQ3191979

Santosh Vempala, Christos H. Papadimitriou

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335320

Mathematics Subject Classification ID

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

Related Items (11)

Improved Lower Bounds on the Approximability of the Traveling Salesman Problem ⋮ Complexity of approximating bounded variants of optimization problems ⋮ Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem ⋮ LP-based solution methods for the asymmetric TSP ⋮ On the approximability of the Steiner tree problem. ⋮ The Steiner tree problem on graphs: inapproximability results ⋮ Approximation algorithms for some vehicle routing problems ⋮ Complexity of the directed spanning cactus problem ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ TSP with bounded metrics ⋮ Approximation algorithms for time-dependent orienteering.

This page was built for publication: On the approximability of the traveling salesman problem (extended abstract)