文章基本信息

标题：Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs
本地全文：下载
作者：Amariah Becker ; Eli Fox-Epstein ; Philip N. Klein 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：75
页码：8:1-8:17
DOI：10.4230/LIPIcs.SEA.2017.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Traveling Salesman; Approximation Schemes; Planar Graph Algorithms; Algorithm Engineering