Improved Inapproximability for TSP
From MaRDI portal
Publication:3167400
DOI10.1007/978-3-642-32512-0_21zbMath1372.68115arXiv1206.2497OpenAlexW3217021010MaRDI QIDQ3167400
Publication date: 2 November 2012
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1206.2497
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Cubic TSP: A 1.3-Approximation ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ New semidefinite programming relaxations for the linear ordering and the traveling salesman problem ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Unnamed Item ⋮ Approximating TSP walks in subcubic graphs
This page was built for publication: Improved Inapproximability for TSP
