Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.

DOI10.1016/S0304-3975(01)00287-0zbMath1094.90036MaRDI QIDQ1608333

Walter Unger, Juraj Hromkovič, Sebastian Seibert, Ralf Klasing, Hans-Joachim Böckenhauer

Publication date: 5 August 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Traveling salesman problemStability of approximation

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27)

Related Items (18)

On the Approximation Ratio of the Path Matching Christofides Algorithm ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality ⋮ Constant factor approximation algorithm for TSP satisfying a biased triangle inequality ⋮ An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality ⋮ On the relationship between ATSP and the cycle cover problem ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ A Modern View on Stability of Approximation ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ On the Hardness of Reoptimization ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Structural Properties of Hard Metric TSP Inputs ⋮ Improved approximations for ordered TSP on near-metric graphs ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance guarantees for the TSP with a parameterized triangle inequality
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• The Euclidean traveling salesman problem is NP-complete
• Lectures on proof verification and approximation algorithms
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• The complexity of theorem-proving procedures

This page was built for publication: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.