Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
DOI10.1007/978-3-319-98355-4_10zbMath1514.68313OpenAlexW2886112286MaRDI QIDQ6163623
Annalisa D'Andrea, Luca Forlizzi, Guido Proietti
Publication date: 30 June 2023
Published in: Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-98355-4_10
relaxed triangle inequalitytraveling salesman path problemminimum-cost Hamiltonian pathreoptimization variantsreoptimization version
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Paths and cycles (05C38) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for the TSP with sharpened triangle inequality
- Steiner tree reoptimization in graphs with sharpened triangle inequality
- Approximating the metric TSP in linear time
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
- Reoptimization of Steiner trees: changing the terminal set
- On \(k\)-connectivity problems with sharpened triangle inequality
- Approximation hardness of deadline-TSP reoptimization
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
- Reoptimization of the metric deadline TSP
- The parameterized approximability of TSP with deadlines
- On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
- New Advances in Reoptimizing the Minimum Steiner Tree Problem
- Reoptimization of Steiner Trees
- Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Reoptimizing the traveling salesman problem
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Eight-Fifth Approximation for the Path TSP
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- On the Approximation Hardness of Some Generalizations of TSP
This page was built for publication: Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
