Geodesic
Probabilistic analysis of decentralized version of оne generalization of the assignment problem
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 11-20

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

A decentralized version of the Semi-Assignment problem is considered, when elements of $m\times n$-matrix are nonnegative, $m=kn$, $k$ is natural number. It is supposed, that $nk$ elements of the matrix are chosen: $k$ elements in each column and one element in each row in order to maximize the total sum of chosen elements. An approximation algorithm with $O(mn)$ time complexity is presented. In the case of inputs, when elements are independent random values with common uniform distribution function, the estimations of a relative error and a fault probability of the algorithm are obtained, and conditions of asymptotic optimality are established. Bibliogr. 8.
Keywords: decentralized transportation problem, NP-hardness, approximation algorithm, asymptotic optimality, Petrov's theorem, uniform distribution. 
@article{DA_2011_18_3_a1,
     author = {E. Kh. Gimadi and V. T. Dementev},
     title = {Probabilistic analysis of decentralized version of {\cyro}ne generalization of the assignment problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {11--20},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_3_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - V. T. Dementev
TI  - Probabilistic analysis of decentralized version of оne generalization of the assignment problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 11
EP  - 20
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_3_a1/
LA  - ru
ID  - DA_2011_18_3_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A V. T. Dementev
%T Probabilistic analysis of decentralized version of оne generalization of the assignment problem
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 11-20
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_3_a1/
%G ru
%F DA_2011_18_3_a1
E. Kh. Gimadi; V. T. Dementev. Probabilistic analysis of decentralized version of оne generalization of the assignment problem. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 11-20. http://geodesic.mathdoc.fr/item/DA_2011_18_3_a1/