Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs
- Becker, Amariah
- Fox-Epstein, Eli
- Klein, Philip N.
- Meierfrankenfeld, David
Publication date
January 2017
DOI Publisher
LIPIcs - Leibniz International Proceedings in Informatics. 16th International Symposium on Experimental Algorithms (SEA 2017)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\u27s guarantee, can quickly find good tours in very large planar graphs
Add to ORKG