Volume 21, No 1, 2014, P. 15–29
UDC 519.8
E. Kh. Gimadi, Yu. V. Glazkov, O. Yu. Tsidulko
The probabilistic analysis of an algorithm for solving the mplanar 3dimensional assignment problem on onecycle permutations
Abstract:
We study the mplanar 3dimensional assignment problem on onecycle permutations. In other words, it is the mperipatetic salesman problem (mPSP) with different weight functions for each salesman. The problem is NPhard for m > 1. We introduce a polynomial approximation algorithm suggested for 1 < m < n/4 with time complexity O(mn^{2}). The performance ratios of the algorithm are established for input data (elements of (m×n×n)matrix) which are assumed to be independent and identically distributed random variables on [a_{n}, b_{n}], where 0 < a_{n} < b_{n}. If the distribution is uniform or dominates the uniform distribution, conditions on an, bn and m are obtained for the asymptotic optimality of the algorithm.
Ill. 1, bibliogr. 26.
Keywords: mplanar 3dimensional assignment problem, onecycle permutations, mPSP with different weight functions, polynomial approximation algorithm, asymptotic optimality.
Gimadi Edward Khairutdinovich ^{1,2}
Glazkov Yury Vladimirovich ^{1}
Tsidulko Oxana Yurievna ^{1}
1. Sobolev Institute of Mathematics,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: gimadi@math.nsc.ru, yg@ngs.ru, tsidulko.ox@gmail.com
