Volume 17, No 3, 2010, P. 19-31

UDC 519.8
E. Kh. Gimadi
On probabilistic analysis of one approximation algorithm for the p-median problem

Abstract:
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.

Gimadi Eduard Khirutdinovich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: gimadi@math.nsc.ru