Approximation Algorithms for the Asymmetric Traveling Salesman Problem: Describing two recent methods

Original · EN

The paper provides a description of the two recent approximation algorithms for the Asymmetric Traveling Salesman Problem, giving the intuitive description of the works of Feige-Singh[1] and Asadpour et.al[2]. [1] improves the previous O(n) approximation algorithm, by improving the constant from 0.84 to 0.66 and modifying the work of Kaplan et. al[3] and also shows an efficient reduction from ATSPP to ATSP. Combining both the results, they finally establish an approximation ratio of (4/3+ε) n for ATSPP,considering a small ε>0,improving the work of Chekuri and Pal.[4] Asadpour et.al, in their seminal work[2], gives an O(n/ n) randomized algorithm for the ATSP, by symmetrizing and modifying the solution of the Held-Karp relaxation problem and then proving an exponential family distribution for probabilistically constructing a maximum entropy spanning tree from a spanning tree polytope and then finally defining the thin-ness property and transforming a thin spanning tree into an Eulerian walk.The optimization methods used in[2] are quite elegant and the approximation ratio could further be improved, by manipulating the thin-ness of the cuts.