License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.8
URN: urn:nbn:de:0030-drops-76305
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7630/
Becker, Amariah ;
Fox-Epstein, Eli ;
Klein, Philip N. ;
Meierfrankenfeld, David
Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs
Abstract
We present an implementation of a linear-time approximation scheme for the traveling salesman problem on planar graphs with edge weights. We observe that the theoretical algorithm involves constants that are too large for practical use. Our implementation, which is not subject to the theoretical algorithm's guarantee, can quickly find good tours in very large planar graphs.
BibTeX - Entry
@InProceedings{becker_et_al:LIPIcs:2017:7630,
author = {Amariah Becker and Eli Fox-Epstein and Philip N. Klein and David Meierfrankenfeld},
title = {{Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {8:1--8:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7630},
URN = {urn:nbn:de:0030-drops-76305},
doi = {10.4230/LIPIcs.SEA.2017.8},
annote = {Keywords: Traveling Salesman, Approximation Schemes, Planar Graph Algorithms, Algorithm Engineering}
}
|
Keywords: |
|
Traveling Salesman, Approximation Schemes, Planar Graph Algorithms, Algorithm Engineering |
|
Collection: |
|
16th International Symposium on Experimental Algorithms (SEA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.08.2017 |
