A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

DOI10.1145/2582112.2582136zbMath1395.68335arXiv1304.1810OpenAlexW1993194903MaRDI QIDQ4635535

Jeff Erickson, Anastasios Sidiropoulos

Publication date: 23 April 2018

Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.1810

zbMATH Keywords

traveling salesmanapproximation algorithmstopological graph algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

Constant Factor Approximation for ATSP with Two Edge Weights ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Constant factor approximation for ATSP with two edge weights

This page was built for publication: A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs