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

DOI10.1145/3309715zbMath1427.90246OpenAlexW2921785090MaRDI QIDQ5244387

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

dynamic programmingapproximation algorithmtraveling salesman problem

Mathematics Subject Classification ID

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

Related Items

A 3/2-Approximation for the Metric Many-Visits Path TSP, A LP-based approximation algorithm for generalized traveling salesperson path problem, The simultaneous semi-random model for TSP, 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 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, 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