From symmetry to asymmetry: generalizing TSP approximations by parametrization

DOI10.1007/978-3-030-86593-1_4MaRDI QIDQ2140484zbMATH OpenOpenAlexFDO

Authors Lukas Behrendt, Katrin Casel, Tobias Friedrich, J. A. Gregor Lagodzinski, Alexander Löser, Marcus Wilhelm

Publication date 20 May 2022

Full work available at URL https://arxiv.org/abs/1911.02453

zbMATH Keywords

parameterized approximationstability of approximationTSP vs. ATSP

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 Dynamic Programming Approach to Sequencing Problems
• A Modern View on Stability of Approximation
• 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
• 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
• 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
• Worst-case analysis of a new heuristic for the travelling salesman problem

Describes a project that uses

Uses Software

• NetworkX
• TSPLIB
• LEMON

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)