On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space
The authors consider the problem of finding \(m\) edge-disjoint salesman tours. The problem is known also as the \(m\)-peripatetic salesman problem (\(m\)-PSP). The problem can be formulated as follows. A complete \(n\)-vertex undirected graph \(G= (V,E)\) is given, where \(V= \{1,\dots, n\}\) is the set of vertices and \(E= \{e= (v,u)\); \(v,u\in V\), \(v< u\}\) is the set of edges. A nonnegative weight function \(w: E\to R_+\) is defined on \(E\). It is required to find \(m\) edge-disjoint traveling salesman tours \(H_1,\dots, H_m\subset E\) such that the total weight of edges in the tours found is maximal. The authors propose an approximation algorithm for solving the \(m\)-PSP in a multidimensional Euclidean space and prove an upper bound for the number \(m\) of tours for which the algorithm gives an asymptotically optimal solution in polynomial time \(O(n^3)\).
- 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
- A heuristic approach to the overnight security service problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
- scientific article; zbMATH DE number 3895002 (Why is no real title available?)
- Job selection and sequencing on a single machine in a random environment
- Lower bounds for symmetricK-peripatetic salesman problems
- The traveling salesman problem and its variations
- An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
- The undirected \(m\)-capacitated peripatetic salesman problem
- Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
- On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
- Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
- On asymptotically optimal approach to the m-Peripatetic Salesman problem on random inputs
- The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms
- Heuristiques pour le Problème du Vendeurm-Péripatétique
- scientific article; zbMATH DE number 4068645 (Why is no real title available?)
- scientific article; zbMATH DE number 1985657 (Why is no real title available?)
- Probabilistic analysis of an approximation algorithm for the m-peripatetic salesman problem on random instances unbounded from above
- Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
- A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
- Approximability of the problem about a minimum-weight cycle cover of a graph
- A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
- 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
- An asymptotically optimal algorithm for the m-peripatetic salesman problem on random inputs with discrete distribution
- Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
- Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean 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)
