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