A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP

DOI10.1134/S1990478919020042zbMath1438.90284OpenAlexW2952489944MaRDI QIDQ4973249

Surèna Garmazhapovna Toktokhoeva, Alekseĭ Nikolaevich 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

approximation algorithmHamiltonian cycletraveling salesman problem\(m\)-peripatetic salesman problemguaranteed approximation ratio

Mathematics Subject Classification ID

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

Related Items (1)

A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP

Cites Work

• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• Better approximations for max TSP
• The traveling salesman problem and its variations
• A heuristic approach to the overnight security service problem
• A 4/5 -- approximation algorithm for the maximum traveling salesman problem
• An Algorithm with Approximation Ratio 5/6 for the Metric Maximum m-PSP
• 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
• Well-solved cases of the 2-peripatetic salesman problem
• Approximation algorithms for the maximum 2-peripatetic salesman 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
• Lower bounds for symmetricK-peripatetic salesman problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP