TY - GEN
T1 - Simpler approximation of the maximum asymmetric traveling salesman problem
AU - Paluch, Katarzyna
AU - Elbassioni, Khaled
AU - Van Zuylen, Anke
PY - 2012
Y1 - 2012
N2 - We give a very simple approximation algorithm for the maximum asymmetric traveling salesman problem. The approximation guarantee of our algorithm is 2/3, which matches the best known approximation guarantee by Kaplan, Lewenstein, Shafrir and Sviridenko. Our algorithm is simple to analyze, and contrary to previous approaches, which need an optimal solution to a linear program, our algorithm is combinatorial and only uses maximum weight perfect matching algorithm.
AB - We give a very simple approximation algorithm for the maximum asymmetric traveling salesman problem. The approximation guarantee of our algorithm is 2/3, which matches the best known approximation guarantee by Kaplan, Lewenstein, Shafrir and Sviridenko. Our algorithm is simple to analyze, and contrary to previous approaches, which need an optimal solution to a linear program, our algorithm is combinatorial and only uses maximum weight perfect matching algorithm.
KW - Approximation algorithm
KW - Maximum asymmetric traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=84876038567&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2012.501
DO - 10.4230/LIPIcs.STACS.2012.501
M3 - Conference contribution
AN - SCOPUS:84876038567
SN - 9783939897354
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 501
EP - 506
BT - 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
T2 - 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
Y2 - 29 February 2012 through 3 March 2012
ER -