Paluch, Katarzyna ;
Elbassioni, Khaled ;
van Zuylen, Anke
Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem
Abstract
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.
BibTeX - Entry
@InProceedings{paluch_et_al:LIPIcs:2012:3412,
author = {Katarzyna Paluch and Khaled Elbassioni and Anke van Zuylen},
title = {{Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {501--506},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3412},
URN = {urn:nbn:de:0030-drops-34129},
doi = {10.4230/LIPIcs.STACS.2012.501},
annote = {Keywords: approximation algorithm, maximum asymmetric traveling salesman problem}
}
|
Keywords: |
|
approximation algorithm, maximum asymmetric traveling salesman problem |
|
Seminar: |
|
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
|
|
Issue date: |
|
2012 |
|
Date of publication: |
|
2012 |
2012
