On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space (Q643801): Difference between revisions

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)\).