An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (extended abstract)
From MaRDI portal
Recommendations
Cited in
(38)- On k-connectivity problems with sharpened triangle inequality
- Estimating the Held-Karp lower bound for the geometric TSP
- An explicit lower bound for TSP with distances one and two
- Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
- Approximation algorithms for the traveling salesman problem
- A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
- Algorithms for the metric ring star problem with fixed edge-cost ratio
- On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
- Weighted amplifiers and inapproximability results for travelling salesman problem
- 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
- On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
- On the approximation ratio of the path matching Christofides algorithm
- Approximation algorithms for the TSP with sharpened triangle inequality
- Structural properties of hard metric TSP inputs (extended abstract)
- Ordered spatial sampling by means of the traveling salesman problem
- Constant factor approximation algorithm for TSP satisfying a biased triangle inequality
- scientific article; zbMATH DE number 4095236 (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
- Approximation Algorithms for the Traveling Salesman Problem with Range Condition
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Improved Approximation Lower Bounds for TSP with Distances One and Two
- New inapproximability bounds for TSP
- On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
- Approximating the Metric TSP in Linear Time
- Analysis of a near-metric TSP approximation algorithm
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- On the Hardness of Reoptimization
- On the Approximation Hardness of Some Generalizations of TSP
- A (slightly) improved approximation algorithm for metric TSP
- Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
- A Modern View on Stability of Approximation
- Approximating the metric TSP in linear time
- 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
- A better differential approximation ratio for symmetric TSP
This page was built for publication: An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501548)
