Approximation algorithms for the TSP with sharpened triangle inequality
DOI10.1016/S0020-0190(00)00089-2zbMATH Open1338.68289OpenAlexW2025698306WikidataQ126550381 ScholiaQ126550381MaRDI QIDQ294819FDOQ294819
Authors: Hans-Joachim Böckenhauer, Ralf Klasing, Sebastian Seibert, Walter Unger, 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
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
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)
Cites Work
- Approximation algorithms for NP-hard problems.
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Faster scaling algorithms for general graph matching problems
- Title not available (Why is that?)
- The Traveling Salesman Problem with Distances One and Two
- Title not available (Why is that?)
- Lectures on proof verification and approximation algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Title not available (Why is that?)
Cited In (28)
- Title not available (Why is that?)
- A Modern View on Stability of Approximation
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
- Hardness and approximation for the star \(\beta \)-hub routing cost problem in \(\varDelta_\beta \)-metric graphs
- Minimum-Weight Cycle Covers and Their Approximability
- On \(k\)-connectivity problems with sharpened triangle inequality
- Approximating the Metric TSP in Linear Time
- On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
- Deterministic algorithms for multi-criteria TSP
- Minimum-weight cycle covers and their approximability
- On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
- Approximation Polynomial Algorithms for Some Modifications of TSP
- Analysis of a near-metric TSP approximation algorithm
- Steiner tree reoptimization in graphs with sharpened triangle inequality
- On the Hardness of Reoptimization
- A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
- Approximability and inapproximability of the star \(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
- Title not available (Why is that?)
- Approximation algorithms for TSP with neighborhoods in the plane
- 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
- Approximation algorithms for time-dependent orienteering.
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) 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)
