|
Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2010, Volume 16, Number 3, Pages 12–24
(Mi timm572)
|
|
|
|
This article is cited in 22 scientific papers (total in 22 papers)
On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space
A. E. Baburin, E. Kh. Gimadia a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
An efficient algorithm $\mathcal A$ with a guaranteed accuracy estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman routes) of maximal weight in a complete weighted undirected graph in a multidimensional Euclidean space $\mathbb R^k$. The complexity of the algorithm is $O(n^3)$. The number of traveling salesman routes for which the algorithm is asymptotically exact is established.
Keywords:
maximum traveling salesman problem, edge-disjoint Hamiltonian circuits, polynomial algorithm, asymptotic accuracy, multidimensional Euclidean space.
Received: 31.03.2010
Citation:
A. E. Baburin, E. Kh. Gimadi, “On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space”, Trudy Inst. Mat. i Mekh. UrO RAN, 16, no. 3, 2010, 12–24; Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S1–S13
Linking options:
https://www.mathnet.ru/eng/timm572 https://www.mathnet.ru/eng/timm/v16/i3/p12
|
Statistics & downloads: |
Abstract page: | 436 | Full-text PDF : | 125 | References: | 59 |
|