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/

[1] Baburin A. E., Gimadi E. Kh., “Priblizhënnyi algoritm otyskaniya $d$-odnorodnogo regulyarnogo ostovnogo svyaznogo podgrafa maksimalnogo vesa v polnom grafe so sluchainymi vesami rëber”, Diskret. analiz i issled. operatsii. Ser. 2, 13:2 (2006), 3–20 | MR

[2] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[3] Gimadi E. Kh., Glebov N. I., Perepelitsa V. A., “Algoritmy s otsenkami dlya zadach diskretnoi optimizatsii”, Problemy kibernetiki, 31, 1975, 35–42

[4] Gimadi E. Kh., “O veroyatnostnom analize priblizhënnogo algoritma resheniya zadachi o $p$-mediane”, Diskret. analiz i issled. operatsii, 17:3 (2010), 19–31 | MR

[5] Deivid G., Poryadkovye statistiki, Nauka, M., 1979, 336 pp. | MR

[6] Dementev V. T., Pyatkin A. V., “O detsentralizovannoi transportnoi zadache”, Diskret. analiz i issled. operatsii, 15:3 (2008), 22–30 | MR

[7] Petrov V. V., Predelnye teoremy dlya summ nezavisimykh sluchainykh velichin, Nauka, M., 1987, 416 pp. | MR

[8] Burkard R., Dell'Amico M., Martello S., Assignment problems, SIAM, Philadelphia, 2009, 378 pp. | MR | Zbl