From symmetry to asymmetry: generalizing TSP approximations by parametrization
From MaRDI portal
Publication:2140484
DOI10.1007/978-3-030-86593-1_4OpenAlexW3201304006MaRDI QIDQ2140484FDOQ2140484
Katrin Casel, Marcus Wilhelm, Lukas Behrendt, Tobias Friedrich, Alexander Löser, J. A. Gregor Lagodzinski
Publication date: 20 May 2022
Full work available at URL: https://arxiv.org/abs/1911.02453
Cites Work
- TSPLIB—A Traveling Salesman Problem Library
- A Dynamic Programming Approach to Sequencing Problems
- Parameterized Algorithms
- Optimum branchings
- On the solution of traveling salesman problems
- Worst-case analysis of a new heuristic for the travelling salesman problem
- 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
Uses Software
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 Q2140484)
