Performance guarantees for the TSP with a parameterized triangle inequality

DOI10.1016/S0020-0190(99)00160-XzbMath1338.68288MaRDI QIDQ294711

Chandra Chekuri, Michael A. Bender

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/S002001909900160X?np=y

zbMATH Keywords

traveling salesman problemapproximation algorithmsrelaxed triangle inequality

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 (21)

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 ⋮ 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 ⋮ 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 ⋮ 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 ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ On the two largest distance eigenvalues of graph powers ⋮ 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

• Unnamed Item
• Unnamed Item
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Finding EPS-graphs
• On spanning subgraphs of a connected bridgeless graph and their application to DT-graphs
• The square of every two-connected graph is Hamiltonian
• NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• The Traveling Salesman Problem with Distances One and Two
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Improved Approximation Algorithms for Uniform Connectivity Problems

This page was built for publication: Performance guarantees for the TSP with a parameterized triangle inequality