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 m-planar 3-dimensional assignment problem on one-cycle permutations

Abstract:
We study the m-planar 3-dimensional assignment problem on one-cycle permutations. In other words, it is the m-peripatetic salesman problem (m-PSP) with different weight functions for each salesman. The problem is NP-hard for m > 1. We introduce a polynomial approximation algorithm suggested for 1 < m < n/4 with time complexity O(mn²). 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: m-planar 3-dimensional assignment problem, one-cycle permutations, m-PSP with different weight functions, polynomial approximation algorithm, asymptotic optimality.

Gimadi Edward Khairutdinovich ^1,2
Glazkov Yury Vladimirovich ¹
Tsidulko Oxana Yurievna ¹
1. Sobolev Institute of Mathematics,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: gimadi@math.nsc.ru, yg@ngs.ru, tsidulko.ox@gmail.com