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

DOI10.1145/2582112.2582136zbMATH Open1395.68335arXiv1304.1810OpenAlexW1993194903MaRDI QIDQ4635535FDOQ4635535

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)

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).

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

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

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)

Cited In (8)

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

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)