A 1.5-Approximation for Path TSP
From MaRDI portal
Publication:5236277
DOI10.1137/1.9781611975482.93zbMath1431.68157arXiv1805.04131OpenAlexW2800453060MaRDI QIDQ5236277
Publication date: 15 October 2019
Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.04131
Related Items (19)
A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable ⋮ The median routing problem for simultaneous planning of emergency response and non-emergency jobs ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ Scheduling on a graph with release times ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem ⋮ An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ 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: A 1.5-Approximation for Path TSP
