Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP

zbMath1403.68355arXiv1707.03992MaRDI QIDQ4608010

Jens Vygen, Vera Traub

Publication date: 15 March 2018

Full work available at URL: https://arxiv.org/abs/1707.03992

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Approximation algorithms (68W25)

Related Items (7)

Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP ⋮ Layers and matroids for the traveling salesman's paths ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ Better \(s-t\)-tours by Gao trees ⋮ An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP

This page was built for publication: Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP