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

DOI10.1145/2582112.2582136MaRDI QIDQ4635535zbMATHOpenAlexFDO

Authors 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

approximation algorithmstraveling salesmantopological graph algorithms

Mathematics Subject Classification ID

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

Abstract: We present a near-optimal polynomial-time approximation algorithm for the asymmetric traveling salesman problem for graphs of bounded orientable or non-orientable genus. Our algorithm achieves an approximation factor of O(f(g)) on graphs with genus g, where f(n) is the best approximation factor achievable in polynomial time on arbitrary n-vertex graphs. In particular, the O(log(n)/loglog(n))-approximation algorithm for general graphs by Asadpour et al. [SODA 2010] immediately implies an O(log(g)/loglog(g))-approximation algorithm for genus-g graphs. Our result improves the O(sqrt(g)*log(g))-approximation algorithm of Oveis Gharan and Saberi [SODA 2011], which applies only to graphs with orientable genus g; ours is the first approximation algorithm for graphs with bounded non-orientable genus. Moreover, using recent progress on approximating the genus of a graph, our O(log(g) / loglog(g))-approximation can be implemented even without an embedding when the input graph has bounded degree. In contrast, the O(sqrt(g)*log(g))-approximation algorithm of Oveis Gharan and Saberi requires a genus-g embedding as part of the input. Finally, our techniques lead to a O(1)-approximation algorithm for ATSP on graphs of genus g, with running time 2^O(g)*n^O(1).

Recommendations

• Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
• The asymmetric traveling salesman problem on graphs with bounded genus
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Approximation algorithms for the bottleneck asymmetric traveling salesman problem

Cited in

(8)

• Constant factor approximation for ATSP with two edge weights
• Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
• The asymmetric traveling salesman problem on graphs with bounded genus
• Approximation algorithms for Euler genus and related problems
• A new approximation algorithm for the asymmetric TSP with triangle inequality
• The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
• Constant factor approximation for ATSP with two edge weights (extended abstract)
• scientific article; zbMATH DE number 2079394 (Why is no real title available?)

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

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