On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space
DOI10.1134/S0081543811020015zbMATH Open1230.65065OpenAlexW2015657372MaRDI QIDQ643801FDOQ643801
Authors: Eh. Kh. Gimadi, Alexei E. Baburin 
Publication date: 2 November 2011
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s0081543811020015
Recommendations
- Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
- Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
- An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
- Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above
- The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms
approximation algorithmasymptotic optimalitymaximum traveling salesman problemedge-disjoint Hamiltonian circuits
Cites Work
- The traveling salesman problem and its variations
- Title not available (Why is that?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Lower bounds for symmetricK-peripatetic salesman problems
- A heuristic approach to the overnight security service problem
- Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
- Job selection and sequencing on a single machine in a random environment
Cited In (20)
- The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms
- Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
- Heuristiques pour le Problème du Vendeurm-Péripatétique
- Title not available (Why is that?)
- On asymptotically optimal approach to the m-Peripatetic Salesman problem on random inputs
- An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
- Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
- A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
- Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
- Approximability of the problem about a minimum-weight cycle cover of a graph
- A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
- The undirected \(m\)-capacitated peripatetic salesman problem
- Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
- An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
- A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
- Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
- Title not available (Why is that?)
- Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above
- Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
- On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
This page was built for publication: On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q643801)
