On the probabilistic analysis of an approximation algorithm for solving the p-median problem
Edward Kh. Gimadi · Journal of Applied and Industrial Mathematics · 2011
In order to solve the location problem in the p-median form we present an approximation algorithm with time complexity O(n 2) and the results of its probabilistic analysis. The input data are defined on a complete graph with distances between the vertices expressed by the independent random variables with the same uniform distribution. The value of the objective function produced by the algorithm amounts to a certain sum of the random variables that we analyze basing on an estimate for the probabilities of large deviations of these sums. We use a limit theorem in the form of the Petrov inequalities, taking into account the dependence of the random variables in the sum. The probabilistic analysis yields some estimates for the relative error and the failure probability of our algorithm, as well as conditions for its asymptotic exactness.