From symmetry to asymmetry: generalizing TSP approximations by parametrization
From MaRDI portal
Publication:6098151
DOI10.1016/J.JCSS.2023.03.007arXiv1911.02453OpenAlexW2985781196MaRDI QIDQ6098151FDOQ6098151
Authors: Lukas Behrendt, Katrin Casel, Tobias Friedrich, J. A. Gregor Lagodzinski, Alexander Löser, Marcus Wilhelm 
Publication date: 12 June 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1911.02453
Cites Work
- TSPLIB—A Traveling Salesman Problem Library
- Encyclopedia of Algorithms
- A Dynamic Programming Approach to Sequencing Problems
- Parameterized algorithms
- Optimum branchings
- On the solution of traveling salesman problems
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- The parameterized approximability of TSP with deadlines
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Transforming asymmetric into symmetric traveling salesman problems
- An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
- Transforming asymmetric into symmetric traveling salesman problems: Erratum
- Title not available (Why is that?)
- New inapproximability bounds for TSP
- Title not available (Why is that?)
- Title not available (Why is that?)
- A (slightly) improved approximation algorithm for metric TSP
- 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
- Time-approximation trade-offs for inapproximable problems
- The effect of the asymmetry of road transportation networks on the traveling salesman problem
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
- Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
- A Modern View on Stability of Approximation
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)
