Approaching 3/2 for the s-t-path TSP

DOI10.1145/3309715MaRDI QIDQ5244387zbMATH OpenOpenAlexFDO

Authors Vera Traub, Jens Vygen

Publication date 21 November 2019

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

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

zbMATH Keywords

approximation algorithmdynamic programmingtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• Approaching 23 for the s-t-path TSP
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Improving Christofides' algorithm for the s-t path TSP
• A 1.5-approximation for path TSP

Cited in

(28)

• Approximation algorithms for general cluster routing problem
• Approximation algorithms with constant ratio for general cluster routing problems
• A LP-based approximation algorithm for generalized traveling salesperson path problem
• The simultaneous semi-random model for TSP
• An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• Improving on best-of-many-Christofides for \(T\)-tours
• An LP-based approximation algorithm for the generalized traveling salesman path problem
• Improving Christofides' algorithm for the s-t path TSP
• Better s-t-tours by Gao trees
• Approaching 23 for the s-t-path TSP
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• Reducing path TSP to TSP
• The salesman's improved paths through forests
• A 1.5-approximation for path TSP
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Reducing Path TSP to TSP
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• An approximation algorithm for the clustered path travelling salesman problem
• Polyhedral techniques in combinatorial optimization: matchings and tours
• Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
• An approximation algorithm for the clustered path travelling salesman problem
• The simultaneous semi-random model for TSP
• Sublinear algorithms and lower bounds for metric TSP cost estimation
• An approximation algorithm for the (metric) clustered path traveling salesman problem
• 1.6-approximation algorithm for generalized traveling salesman path problem
• Better approximation algorithms for clustered TSP and subgroup planning

This page was built for publication: Approaching 3/2 for the \(s\)-\(t\)-path TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5244387)