From symmetry to asymmetry: generalizing TSP approximations by parametrization
From MaRDI portal
Publication:6098151
Abstract: We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymmetric distances in the given instance, which yields algorithms to efficiently compute constant factor approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric edges. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the number of asymmetric edges in a given minimum spanning arborescence. Both algorithms are also stated in the form of additive lossy kernelizations, which allows to combine them with known polynomial time approximations for ATSP. Further, we combine them with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. We complement our results by experimental evaluations, which show that generalized tree-doubling frequently outperforms generalized Christofides with respect to parameter size.
Cites work
- scientific article; zbMATH DE number 2086388 (Why is no real title available?)
- scientific article; zbMATH DE number 3298367 (Why is no real title available?)
- scientific article; zbMATH DE number 3335671 (Why is no real title available?)
- A (slightly) improved approximation algorithm for metric TSP
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- A Modern View on Stability of Approximation
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
- An improved approximation algorithm for ATSP
- An improved approximation algorithm for the ATSP with parameterized triangle inequality
- An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Encyclopedia of Algorithms
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- New inapproximability bounds for TSP
- On the solution of traveling salesman problems
- Optimum branchings
- Parameterized algorithms
- TSPLIB—A Traveling Salesman Problem Library
- The effect of the asymmetry of road transportation networks on the traveling salesman problem
- The parameterized approximability of TSP with deadlines
- Time-approximation trade-offs for inapproximable problems
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
- Transforming asymmetric into symmetric traveling salesman problems
- Transforming asymmetric into symmetric traveling salesman problems: Erratum
- Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
This page was built for publication: From symmetry to asymmetry: generalizing TSP approximations by parametrization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098151)
