A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
From MaRDI portal
Publication:2009011
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
approximation algorithmtraveling salesman problemperformance guaranteerelaxed \(\triangle\)-inequalitytraveling salesman path problem
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
