A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
type: Item
instance of: scholarly article
title: A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
zbMATH Open document ID: 1433.90140
author: Usha Mohan
author: Sivaramakrishnan Ramani
author: Sounaka Mishra
published in: Discrete Applied Mathematics
publication date: 2019-11-27T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7136948
zbMATH Keywords: traveling salesman problem
zbMATH Keywords: traveling salesman path problem
zbMATH Keywords: relaxed \(\triangle\)-inequality
zbMATH Keywords: approximation algorithm
zbMATH Keywords: performance guarantee
MaRDI profile type: Publication
full work available at URL: j.dam.2019.08.007
OpenAlex ID: W2969517824
cites work: Improving Christofides' Algorithm for the s-t Path TSP
cites work: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
cites work: Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
cites work: Performance guarantees for the TSP with a parameterized triangle inequality
cites work: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
cites work: Q3415353
cites work: An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
cites work: On the Metric $s$--$t$ Path Traveling Salesman Problem
cites work: Better s-t-Tours by Gao Trees
cites work: Analysis of Christofides' heuristic: some paths are more difficult than cycles
cites work: Q3693290
cites work: Ottimizzazione Combinatoria
cites work: Constant factor approximation algorithm for TSP satisfying a biased triangle inequality
cites work: An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
cites work: P-Complete Approximation Problems
cites work: Eight-Fifth Approximation for the Path TSP
cites work: Approximating the Bipartite TSP and Its Biased Generalization
cites work: Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP
cites work: Reassembling trees for the traveling salesman
cites work: A 1.5-Approximation for Path TSP
DOI: 10.1016/J.DAM.2019.08.007
description: scientific article; zbMATH DE number 7136948