Approximation algorithms for the TSP with sharpened triangle inequality

DOI10.1016/S0020-0190(00)00089-2zbMath1338.68289OpenAlexW2025698306WikidataQ126550381 ScholiaQ126550381MaRDI QIDQ294819

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

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000000892?np=y

zbMATH Keywords

combinatorial problemstraveling salesman problemapproximation algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (20)

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 ⋮ On the approximability of the single allocation \(p\)-hub center problem with parameterized 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 ⋮ Complexity and approximability of extended spanning star forest problems in general and complete graphs ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ Minimum-Weight Cycle Covers and Their Approximability ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ A Modern View on Stability of Approximation ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ 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 ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Minimum-weight cycle covers and their approximability ⋮ Approximation algorithms for time-dependent orienteering.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lectures on proof verification and approximation algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Faster scaling algorithms for general graph matching problems
• The Traveling Salesman Problem with Distances One and Two
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities

This page was built for publication: Approximation algorithms for the TSP with sharpened triangle inequality