2026-07-20T06:35:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7630 2024-03-06T10:39:47Z ddc:004 open_access

Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs Becker, Amariah Fox-Epstein, Eli Klein, Philip N. Meierfrankenfeld, David Traveling Salesman Approximation Schemes Planar Graph Algorithms Algorithm Engineering 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amariah Becker and Eli Fox-Epstein and Philip N. Klein and David Meierfrankenfeld 2017 Is Part Of LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2017.8 urn:nbn:de:0030-drops-76305 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode