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

DOI10.1016/j.dam.2019.08.007zbMath1433.90140OpenAlexW2969517824MaRDI QIDQ2009011

Sivaramakrishnan Ramani, Sounaka Mishra, Usha Mohan

Publication date: 27 November 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.08.007

zbMATH Keywords

approximation algorithmtraveling salesman problemperformance guaranteerelaxed \(\triangle\)-inequalitytraveling salesman path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Performance guarantees for the TSP with a parameterized triangle inequality
• Constant factor approximation algorithm for TSP satisfying a biased 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.
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Reassembling Trees for the Traveling Salesman
• Improving Christofides' Algorithm for the s-t Path TSP
• Better s-t-Tours by Gao Trees
• Ottimizzazione Combinatoria
• P-Complete Approximation Problems
• Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Eight-Fifth Approximation for the Path TSP
• A 1.5-Approximation for Path TSP
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• Approximating the Bipartite TSP and Its Biased Generalization

This page was built for publication: A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality