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

DOI10.1134/S199047891501007XMaRDI QIDQ5264766zbMATH OpenOpenAlexFDO

Authors D. Zh. Zambalaeva, A. A. Skretneva, A. N. 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

traveling salesman problemdirected graphpolynomial algorithm2-peripatetic salesman problemguaranteed accuracy bound

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6007907
• A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the m-PSP
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
• scientific article; zbMATH DE number 5899262
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems

Cites work

• scientific article; zbMATH DE number 6007907 (Why is no real title available?)
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Bounds for the symmetric 2-peripatetic salesman problem
• Lower bounds for symmetricK-peripatetic salesman problems

Cited in

(7)

• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• 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
• scientific article; zbMATH DE number 6007907 (Why is no real title available?)
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph

This page was built for publication: A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem

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