Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.501
URN: urn:nbn:de:0030-drops-34129
URL: https://drops.dagstuhl.de/opus/volltexte/2012/3412/
Paluch, Katarzyna ; Elbassioni, Khaled ; van Zuylen, Anke
Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem
| pdf-format: |
|
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: | 24.02.2012 |
