On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space (Q643801)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space |
scientific article |
Statements
On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space (English)
0 references
2 November 2011
0 references
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)\).
0 references
maximum traveling salesman problem
0 references
edge-disjoint Hamiltonian circuits
0 references
asymptotic optimality
0 references
approximation algorithm
0 references