The Salesman’s Improved Paths through Forests

DOI10.1145/3326123zbMath1479.90180OpenAlexW2950127069MaRDI QIDQ5215457

András Sebő, Anke van Zuylen

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3326123

zbMATH Keywords

integrality gappath traveling salesman problem (TSP)Christofides-Serdyukov heuristiclinear programming relaxations and rounding algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (11)

A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ Approximation algorithms for general cluster routing problem ⋮ Approximation algorithms with constant ratio for general cluster routing problems ⋮ Reducing Path TSP to TSP ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

This page was built for publication: The Salesman’s Improved Paths through Forests