Constant factor approximation algorithm for TSP satisfying a biased triangle inequality
From MaRDI portal
Publication:346242
DOI10.1016/j.tcs.2016.09.017zbMath1355.90086OpenAlexW2528652158MaRDI QIDQ346242
Sounaka Mishra, Usha Mohan, Sivaramakrishnan Ramani
Publication date: 5 December 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.09.017
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Performance guarantees for the TSP with a parameterized triangle inequality
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
- On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- P-Complete Approximation Problems
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Approximating the Bipartite TSP and Its Biased Generalization
This page was built for publication: Constant factor approximation algorithm for TSP satisfying a biased triangle inequality