Engineering an approximation scheme for traveling salesman in planar graphs

DOI10.4230/LIPICS.SEA.2017.8zbMATH Open1432.68566OpenAlexW2750610069MaRDI QIDQ4580152FDOQ4580152

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

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

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)

Cited In (3)

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

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)