A constant-factor approximation algorithm for the asymmetric traveling salesman problem
From MaRDI portal
Abstract: We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. The main idea of our approach is a reduction to Subtour Partition Cover, an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. We first show that any algorithm for Subtour Partition Cover can be turned into an algorithm for ATSP while only losing a small constant factor in the performance guarantee. Next, we present a reduction from general ATSP instances to structured instances, on which we then solve Subtour Partition Cover, yielding our constant-factor approximation algorithm for ATSP.
Recommendations
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- Constant factor approximation for ATSP with two edge weights (extended abstract)
- Constant factor approximation for ATSP with two edge weights
- The asymmetric traveling salesman problem on graphs with bounded genus
- scientific article; zbMATH DE number 1445294
Cited in
(33)- Constant factor approximation for ATSP with two edge weights
- Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem
- The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem
- A constant-factor approximation for directed latency in quasi-polynomial time
- Minimizing the makespan on a single machine subject to modular setups
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Search and delivery man problems: when are depth-first paths optimal?
- Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
- scientific article; zbMATH DE number 5899262 (Why is no real title available?)
- Constant factor approximation for ATSP with two edge weights (extended abstract)
- Approximation algorithms for the single robot line coverage problem
- Approximation algorithms for the bottleneck asymmetric traveling salesman problem
- Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
- scientific article; zbMATH DE number 6178353 (Why is no real title available?)
- scientific article; zbMATH DE number 1445294 (Why is no real title available?)
- Thin trees in some families of distance-regular graphs
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems
- The asymmetric traveling salesman problem on graphs with bounded genus
- An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
- A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
- Collapsing Superstring Conjecture
- The temporal explorer who returns to the base
- FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
- Polyhedral techniques in combinatorial optimization: matchings and tours
- Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
- Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
- The single robot line coverage problem: Theory, algorithms, and experiments
- Approximation algorithms with constant factors for a series of asymmetric routing problems
- The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
- Constant-factor approximation to deadline TSP and related problems in (almost) quasi-polytime
- Implementation and numerical evaluation of Traub and Vygen algorithm for the subtour cover problem
This page was built for publication: A constant-factor 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 Q5230290)
