Engineering an approximation scheme for traveling salesman in planar graphs

DOI10.4230/LIPICS.SEA.2017.8MaRDI QIDQ4580152zbMATH OpenOpenAlexFDO

Authors Amariah Becker, Eli Fox-Epstein, David Meierfrankenfeld, Philip N. Klein

Publication date 13 August 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.SEA.2017.8

zbMATH Keywords

approximation schemestraveling salesmanalgorithm engineeringplanar graph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• scientific article; zbMATH DE number 1303538
• An approximation algorithm for the TSP
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• scientific article; zbMATH DE number 2080248

Cited in

(3)

• Novel concave hull-based heuristic algorithm for TSP
• Approximate Mechanisms for the Graphical TSP and Other Graph-Traversal Problems
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights

This page was built for publication: Engineering an approximation scheme for traveling salesman in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580152)