Constant factor approximation algorithm for TSP satisfying a biased triangle inequality

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

zbMATH Keywords

TSPapproximation algorithmsrelaxed triangle inequality

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality

Uses Software

• Concorde

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