New Inapproximability Bounds for TSP

DOI10.1007/978-3-642-45030-3_53zbMath1328.68075arXiv1303.6437OpenAlexW2569455461MaRDI QIDQ2872120

Michael Lampis, Richard Schmied, Marek Karpinski

Publication date: 14 January 2014

Published in: Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Traveling salesman problems in temporal graphs ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Approximation hardness of graphic TSP on cubic graphs ⋮ Time-approximation trade-offs for inapproximable problems ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ Robust Algorithms for TSP and Steiner Tree ⋮ Affine reductions for LPs and SDPs ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ New Approximation Algorithms for (1,2)-TSP ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ Towards better models of externalities in sponsored search auctions ⋮ No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem ⋮ Reassembling Trees for the Traveling Salesman

This page was built for publication: New Inapproximability Bounds for TSP