A 5/8 approximation algorithm for the maximum asymmetric traveling salesperson problem

A 5/8 approximation algorithm for the maximum asymmetric traveling salesperson problem

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.