An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
DOI10.1287/opre.2017.1603zbMath1380.90229OpenAlexW2620774153WikidataQ94086899 ScholiaQ94086899MaRDI QIDQ5360842
Michel X. Goemans, Arash Asadpour, Amin Saberi, Shayan Oveis Gharan, Aleksander Mądry
Publication date: 26 September 2017
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.2017.1603
linear programmingmaximum entropytraveling salesman problemrandomized roundingHeld-Karp relaxationthin tree
Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (14)
This page was built for publication: An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem