On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space

作     者：Baburin, A. E. Gimadi, E. Kh 

作者机构：Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk 630090 Russia 

出 版 物：《PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS》 (斯捷克洛夫数学研究所汇报)

年 卷 期：2011年第272卷第1-Sup期

页      面：1-13页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Russian Foundation for Basic Research [08-01-00516, 10-07-00195] Presidium of the Russian Academy of Sciences [2, 227] Siberian Branch of the Russian Academy of Sciences 

主　　题：maximum traveling salesman problem edge-disjoint Hamiltonian circuits polynomial-time algorithm asymptotic optimality multidimensional Euclidean space 

摘      要：An efficient algorithm A with a guaranteed error estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman tours) of maximum weight in a complete weighted undirected graph in a multidimensional Euclidean space ae (k) . The time complexity of the algorithm is O(n (3)). The number of traveling salesman tours for which the algorithm is asymptotically optimal is established.