Article ID: | iaor2006623 |
Country: | United States |
Volume: | 17 |
Issue: | 2 |
Start Page Number: | 237 |
End Page Number: | 248 |
Publication Date: | Jan 2003 |
Journal: | SIAM Journal on Discrete Mathematics |
Authors: | Lewenstein M., Sviridenko M. |
Keywords: | heuristics |
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 by Kosaraju, Park, and Stein.