Improving Christofides' Algorithm for the s-t Path TSP
From MaRDI portal
Publication:3177743
DOI10.1145/2818310zbMath1426.68300arXiv1110.4604OpenAlexW2240814884MaRDI QIDQ3177743
Hyung-Chan An, David B. Shmoys, Robert D. Kleinberg
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.4604
Related Items (21)
A constant-factor approximation for directed latency in quasi-polynomial time ⋮ 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 ⋮ Layers and matroids for the traveling salesman's paths ⋮ An approximation algorithm for the clustered path travelling salesman 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 ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ Scheduling on a graph with release times ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem ⋮ 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 ⋮ 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: Improving Christofides' Algorithm for the s-t Path TSP
