On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
From MaRDI portal
Publication:2748380
DOI10.1002/net.1024zbMath0996.90086OpenAlexW1977056448MaRDI QIDQ2748380
Publication date: 14 October 2001
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.1024
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (25)
On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality ⋮ On the Approximation Ratio of the Path Matching Christofides Algorithm ⋮ 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 ⋮ Symmetric connectivity with directional antennas ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ Improved approximations for TSP with simple precedence constraints ⋮ Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions ⋮ Solving nonlinear and dynamic programming equations on extended \(b\)-metric spaces with the fixed-point technique ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ A Modern View on Stability of Approximation ⋮ The minimum-area spanning tree problem ⋮ Relaxed triangle inequality ratio of the Sørensen-Dice and Tversky indexes ⋮ Approximating the metric TSP in linear time ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Improved approximations for ordered TSP on near-metric graphs ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality ⋮ Approximate spanning cactus ⋮ Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
Cites Work
- Approximation algorithms for multi-dimensional assignment problems with decomposable costs
- Minimum transversals of maximum matchings as approximate solutions to the bisection problem
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Unnamed Item
- Unnamed Item
This page was built for publication: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
