Approximation algorithms for the TSP with sharpened triangle inequality
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1500530
- scientific article; zbMATH DE number 4095236
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
- An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
Cites work
- Approximation algorithms for NP-hard problems.
- Faster scaling algorithms for general graph matching problems
- scientific article; zbMATH DE number 2185604 (Why is no real title available?)
- scientific article; zbMATH DE number 3898613 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1500530 (Why is no real title available?)
- scientific article; zbMATH DE number 3409134 (Why is no real title available?)
- Lectures on proof verification and approximation algorithms
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- The Traveling Salesman Problem with Distances One and Two
Cited in
(31)- On k-connectivity problems with sharpened triangle inequality
- Minimum-weight cycle covers and their approximability
- Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
- Approximation algorithms for time-dependent orienteering.
- On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
- Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
- An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- Approximation algorithms for TSP with neighborhoods in the plane
- Deterministic algorithms for multi-criteria TSP
- Minimum-Weight Cycle Covers and Their Approximability
- Steiner tree reoptimization in graphs with sharpened triangle inequality
- scientific article; zbMATH DE number 1985657 (Why is no real title available?)
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- scientific article; zbMATH DE number 1500530 (Why is no real title available?)
- scientific article; zbMATH DE number 1507218 (Why is no real title available?)
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
- Approximating the Metric TSP in Linear Time
- Approximation Polynomial Algorithms for Some Modifications of TSP
- Analysis of a near-metric TSP approximation algorithm
- On the Hardness of Reoptimization
- A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
- Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
- A Modern View on Stability of Approximation
- Hardness and approximation for the star -hub routing cost problem in _ -metric graphs
- On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
- Some worst-case results related to the asymmetric traveling salesman problem
- An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
- On the relationship between ATSP and the cycle cover problem
This page was built for publication: Approximation algorithms for the TSP with sharpened triangle inequality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294819)
