A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem
classification
💻 cs.DS
keywords
algorithmalgorithmsasymmetricproblemrandomizedroundingsalesmantraveling
read the original abstract
We present an algorithm for the asymmetric traveling salesman problem on instances which satisfy the triangle inequality. Like several existing algorithms, it achieves approximation ratio O(log n). Unlike previous algorithms, it uses randomized rounding.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.