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

zbMATH Keywords

linear programmingmaximum entropytraveling salesman problemrandomized roundingHeld-Karp relaxationthin tree

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (14)

Maximum entropy and integer partitions ⋮ On the Computability of Continuous Maximum Entropy Distributions with Applications ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ The simultaneous semi-random model for TSP ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ The indefinite period traveling salesman problem ⋮ The temporal explorer who returns to the base ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes ⋮ Efficient Large-Scale Multi-Drone Delivery using Transit Networks ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

This page was built for publication: An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem