Geodesic
On probabilistic analysis of one approximation algorithm for the $p$-median problem
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 3, pp. 19-31.

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

An approximation algorithm for solving the $p$-median problem with time complexity $O(n^2)$ and results of its probabilistic analysis are presented. Given an undirected complete graph with distances that are independent random uniformly distributed variables. The objective equals the sum of the random variables. Analysis is based on estimations of the probability of great deviations of those sums. In the paper one of limit theorems for this analysis in the form of Petrov's inequality is used. Moreover, the dependence factor is taken into account. As the results of the probabilistic analysis, the bounds of the relative error, the fault probability and conditions of asymptotic optimality of the algorithm are presented. Ill. 1, bibl. 11.
Keywords: $p$-median problem, approximation algorithm, asymptotic optimality, relative error, fault probability, Petrov's theorem, uniform distribution. 
@article{DA_2010_17_3_a1,
     author = {E. Kh. Gimadi},
     title = {On probabilistic analysis of one approximation algorithm for the $p$-median problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {19--31},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_3_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
TI  - On probabilistic analysis of one approximation algorithm for the $p$-median problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 19
EP  - 31
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_3_a1/
LA  - ru
ID  - DA_2010_17_3_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%T On probabilistic analysis of one approximation algorithm for the $p$-median problem
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 19-31
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_3_a1/
%G ru
%F DA_2010_17_3_a1
E. Kh. Gimadi. On probabilistic analysis of one approximation algorithm for the $p$-median problem. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 3, pp. 19-31. http://geodesic.mathdoc.fr/item/DA_2010_17_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] Gimadi E. Kh., Glebov N. I., Perepelitsa V. A., “Algoritmy s otsenkami dlya zadach diskretnoi optimizatsii”, Problemy kibernetiki, 31, 1975, 35–42

[3] Gimadi E. Kh., Perepelitsa V. A., “Asimptoticheski tochnyi podkhod k resheniyu zadachi kommivoyazhera”, Upravlyaemye sistemy, 12, In-t matematiki SO AN SSSR, Novosibirsk, 1974, 35–45 | Zbl

[4] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Per. s angl., Mir, M., 1982, 416 pp. | MR

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

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

[7] Angluin D., Valiant L. G., “Fast probabilistic algorithms for Hamiltonian circuits and matchings”, J. Comput. System Sci., 18 (1979), 155–193 | DOI | MR | Zbl

[8] Mirchandani P. B., Francis R. L. (eds.), Discrete Location Theory, Wiley-Interscience Publication, Wiley and Sons Inc., 1990, 557 pp. | MR | Zbl

[9] Frieze A., “On random symmetric travelling salesman problems”, Math. Oper. Research, 29:4 (2004), 878–890 | DOI | MR | Zbl

[10] Karp R. M., “The probabilistic analysis of some combinatorial search algorithms”, Algorithms and complexity: new directions and recent results, ed. Traub J. P., Acad. Press, New York, 1976, 1–19 | MR

[11] Slominski L., “Probabilistic analysis of combinatorial algorithms: a bibliography with selected annotations”, Computing, 28 (1982), 257–267 | DOI | MR | Zbl