Performance guarantees for the TSP with a parameterized triangle inequality

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

Recommendations

On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
scientific article; zbMATH DE number 2038707

Cites work

Finding EPS-graphs
Guaranteed performance heuristics for the bottleneck traveling salesman problem
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
scientific article; zbMATH DE number 1163704 (Why is no real title available?)
scientific article; zbMATH DE number 3192675 (Why is no real title available?)
Improved Approximation Algorithms for Uniform Connectivity Problems
NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
On spanning subgraphs of a connected bridgeless graph and their application to DT-graphs
Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
The square of every two-connected graph is Hamiltonian
The Traveling Salesman Problem with Distances One and Two

Cited in

(27)

On k-connectivity problems with sharpened triangle inequality
Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
Relaxed triangle inequality ratio of the Sørensen-Dice and Tversky indexes
A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
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
Approximate spanning cactus
The minimum-area spanning tree problem
On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
On the approximation ratio of the path matching Christofides algorithm
Improved approximations for hard optimization problems via problem instance classification
Constant factor approximation algorithm for TSP satisfying a biased triangle inequality
Symmetric connectivity with directional antennas
Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
On the two largest distance eigenvalues of graph powers
Improved approximations for ordered TSP on near-metric graphs
On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
A Modern View on Stability of Approximation
On a traveling salesman problem for points in the unit cube
Algebraic bounds for the independence and chromatic number of graph powers
On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs
An FPT factor-11 approximation algorithm for TSP
On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
On the relationship between ATSP and the cycle cover problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294711)