Dan A. Iancu, Mayank Sharma, et al.
Operations Research
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].
Dan A. Iancu, Mayank Sharma, et al.
Operations Research
Nikhil Bansal, Mohammad Mahdian, et al.
Mathematics of Operations Research
Sungjin Im, Maxim Sviridenko, et al.
STACS 2012
Alexander Grigoriev, Maxim Sviridenko, et al.
Mathematical Programming