A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
From MaRDI portal
Publication:5264766
DOI10.1134/S199047891501007XzbMath1324.90182OpenAlexW2088833374MaRDI QIDQ5264766
A. A. Skretneva, D. Zh. Zambalaeva, Alekseĭ Nikolaevich Glebov
Publication date: 27 July 2015
Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s199047891501007x
directed graphtraveling salesman problempolynomial algorithm2-peripatetic salesman problemguaranteed accuracy bound
Related Items (2)
A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
Cites Work
- Unnamed Item
- A branch and bound algorithm for symmetric 2-peripatetic salesman problems
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- Bounds for the symmetric 2-peripatetic salesman problem
- Lower bounds for symmetricK-peripatetic salesman problems
This page was built for publication: A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem