Geodesic
The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 1, pp. 15-29

Voir la notice de l'article provenant de la source Math-Net.Ru

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\ge1$. We introduce a polynomial approximation algorithm suggested for $1$ with time complexity $O(mn^2)$. The performance ratios of the algorithm are established for input data (elements of $(m\times n\times n)$-matrix) which are assumed to be independent and identically distributed random variables on $[a_n,b_n]$, where $0$. If the distribution is uniform or dominates the uniform distribution, conditions on $a_n,b_n$ and $m$ are obtained for the asymptotic optimality of the algorithm. Ill. 1, bibliogr. 26.
Keywords: $m$-planar $3$-dimensional assignment problem, $m$-PSP with different weight functions, asymptotic optimality.
Mots-clés : one-cycle permutations, polynomial approximation algorithm 
@article{DA_2014_21_1_a1,
     author = {E. Kh. Gimadi and Yu. V. Glazkov and O. Yu. Tsidulko},
     title = {The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {15--29},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_1_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - Yu. V. Glazkov
AU  - O. Yu. Tsidulko
TI  - The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 15
EP  - 29
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_1_a1/
LA  - ru
ID  - DA_2014_21_1_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A Yu. V. Glazkov
%A O. Yu. Tsidulko
%T The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 15-29
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_1_a1/
%G ru
%F DA_2014_21_1_a1
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. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 1, pp. 15-29. http://geodesic.mathdoc.fr/item/DA_2014_21_1_a1/