A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
From MaRDI portal
Publication:4973249
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
approximation algorithmHamiltonian cycletraveling salesman problem\(m\)-peripatetic salesman problemguaranteed approximation ratio
Related Items
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