Matroid matching: The power of local search
Jon Lee, Maxim Sviridenko, et al.
STOC 2010
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.
STOC 2010
Wenhua Li, Maurice Queyranne, et al.
Journal of Scheduling
Amihood Amir, Dmitry Keselman, et al.
Journal of Algorithms
Dan A. Iancu, Mayank Sharma, et al.
Operations Research