A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem

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

zbMATH Keywords

directed graphtraveling salesman problempolynomial algorithm2-peripatetic salesman problemguaranteed accuracy bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

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