Approximating asymmetric TSP in exponential time

DOI10.1142/S0129054114500051MaRDI QIDQ5168426zbMATH OpenFDO

Authors Alexander Golovnev

Publication date 4 July 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054114500051

zbMATH Keywords

approximation schemeasymmetric traveling salesman problemexponential-time algorithmtraveling salesman problemTSP

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• An approximation algorithm for the TSP
• scientific article; zbMATH DE number 4095236
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• scientific article; zbMATH DE number 5899262

Cites work

• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Exact algorithms for exact satisfiability and number of perfect matchings
• Expected Computation Time for Hamiltonian Path problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• P-Complete Approximation Problems
• The traveling-salesman problem and minimum spanning trees: Part II

Cited in

(9)

• Upper bounds on ATSP neighborhood size.
• Many-visits TSP revisited
• An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation
• scientific article; zbMATH DE number 2079394 (Why is no real title available?)
• A new approximation algorithm for the asymmetric TSP with triangle inequality
• Time- and space-optimal algorithm for the many-visits TSP
• A time- and space-optimal algorithm for the many-visits TSP
• The Clustered Selected-Internal Steiner Tree Problem
• Exponential time approximation scheme for TSP

This page was built for publication: Approximating asymmetric TSP in exponential time

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