CATS-Apr-22-2016
Title[edit]
Approximating the ATSP on topologically restricted graphs
Speaker[edit]
Ahmed Abdelkader
Abstract[edit]
We review recent work on ATSP starting with the O(log n / log log n)-approximation by Asadpour et al. [1], which was the first asymptotic improvement in almost 30 years. The key ingredient is the notion of thin trees, which they obtain by post-processing a solution to the Held-Karp relaxation. We proceed to describe how this notion was further applied to get better approximations for graphs of bounded genus by Oveis Gharan and Saberi [2] and Erickson and Sidiropoulos [3]. Finally, we discuss a recent preprint by Marx, Salmasi and Sidiropoulos [4], which combines thin trees with a dynamic program to handle the larger class of nearly-embeddable graphs.
[1] Asadpour, Arash, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. "An O (log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem." In SODA, vol. 10, pp. 379-389. 2010.
[2] Gharan, Shayan Oveis, and Amin Saberi. "The asymmetric traveling salesman problem on graphs with bounded genus." In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 967-975. SIAM, 2011.
[3] Erickson, Jeff, and Anastasios Sidiropoulos. "A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs." In Proceedings of the thirtieth annual symposium on Computational geometry, p. 130. ACM, 2014.
[4] Marx, Dániel and Ario Salmasi, Anastasios Sidiropoulos. "Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs." CoRR, abs/1601.01372, 2016.
