A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP
From MaRDI portal
Publication:5090157
DOI10.33048/daio.2020.27.677zbMath1495.90152OpenAlexW3112416390MaRDI QIDQ5090157
Surèna Garmazhapovna Toktokhoeva, Alekseĭ Nikolaevich Glebov
Publication date: 15 July 2022
Published in: Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)
Full work available at URL: http://mathnet.ru/eng/da955
approximation algorithmHamiltonian cycletraveling salesman problem\(m\)-peripatetic salesman problemguaranteed approximation ratio
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- \(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
- A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
- 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
- Lower bounds for symmetricK-peripatetic salesman problems
