An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

DOI10.1137/20M1339313OpenAlexW4213165341MaRDI QIDQ5863328FDOQ5863328

Authors: Vera Traub, Jens Vygen 

Publication date: 11 March 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1339313

Recommendations

• An improved approximation algorithm for ATSP
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem

zbMATH Keywords

approximation algorithmstraveling salesman problemintegrality ratio

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• Eight-fifth approximation for the path TSP
• New inapproximability bounds for TSP
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Better \(s-t\)-tours by Gao trees
• Constant factor approximation for ATSP with two edge weights
• \(\frac{13}{9}\)-approximation for graphic TSP
• Reassembling trees for the traveling salesman
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Removing and adding edges for the traveling salesman problem
• A 1.5-approximation for path TSP
• The salesman's improved paths through forests
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Title not available (Why is that?)
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• An improved approximation algorithm for TSP in the half integral case
• Title not available (Why is that?)
• Reducing path TSP to TSP

Cited In (21)

• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• Title not available (Why is that?)
• Title not available (Why is that?)
• Evaluation of The Contract Or-Patch Heuristic Eor The Asymmetric Tsp¹
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem
• The on-line asymmetric traveling salesman problem
• Approximations for the Steiner multicycle problem
• Title not available (Why is that?)
• Approximation algorithms with constant factors for a series of asymmetric routing problems
• Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles
• A new approximation algorithm for the asymmetric TSP with triangle inequality
• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• Improved first player strategy for the zero-sum sequential uncrossing game
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem
• An effective hybrid harmony search for the asymmetric travelling salesman problem
• Algorithms and Data Structures
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• Title not available (Why is that?)

This page was built for publication: An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

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