2014/05/08 by Bhattacharya, Arka
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1405.1781
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].\newline [1] improves the previous O(log 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)+ε)log n for ATSPP, considering a small ε>0, improving the work of Chekuri and Pal.[4]\newline Asadpour et.al, in their seminal work [2], gives an O((log n)/(log log 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.