A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP

DOI10.1134/S1990478919020042MaRDI QIDQ4973249zbMATH OpenOpenAlexFDO

Authors Surèna Garmazhapovna Toktokhoeva, A. N. Glebov

Publication date 2 December 2019

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1990478919020042

zbMATH Keywords

\(m\)-peripatetic salesman problemapproximation algorithmguaranteed approximation ratioHamiltonian cycletraveling salesman problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the m-PSP
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality

Cites work

• \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions
• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• A 4/5 -- approximation algorithm for the maximum traveling salesman problem
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• A heuristic approach to the overnight security service problem
• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An algorithm with approximation ratio 5/6 for the metric maximum m-PSP
• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• Better approximations for max TSP
• Bounds for the symmetric 2-peripatetic salesman problem
• scientific article; zbMATH DE number 6007907 (Why is no real title available?)
• scientific article; zbMATH DE number 6004865 (Why is no real title available?)
• scientific article; zbMATH DE number 3910163 (Why is no real title available?)
• scientific article; zbMATH DE number 3485514 (Why is no real title available?)
• scientific article; zbMATH DE number 2102640 (Why is no real title available?)
• Lower bounds for symmetricK-peripatetic salesman problems
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• The traveling salesman problem and its variations
• Well-solved cases of the 2-peripatetic salesman problem

Cited in

(2)

• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the m-PSP

This page was built for publication: A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP

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