Jon Lee, Maxim Sviridenko, et al.
SIAM Journal on Computing
The maximum asymmetric traveling salesperson problem, also known as the taxicab rip-off problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with nonnegative weights. We propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. This (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. Our solution uses a simple linear programming formulation. Previous solutions were combinatorial. We make use of the linear programming in a novel manner and strengthen the path-coloring method originally proposed in [S. R. Kosaraju, J. K. Park, and C. Stein, Long tours and short superstrings, in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166-177].
Jon Lee, Maxim Sviridenko, et al.
SIAM Journal on Computing
Haim Kaplan, Moshe Lewenstein, et al.
FOCS 2003
Tracy Kimbrel, Baruch Schieber, et al.
SODA 2004
Alexander Kononov, Sergey Sevastyanov, et al.
Journal of Scheduling