Probabilistic Analysis of a Relaxation for the K-Median Problem -The Euclidean Model in the Plane

Abstract

The k-median problem has been widely studied both from the theoretical

point of view and for its applications. An interesting theoretical development

was the successful probabilistic analysis of several heuristics for this problem

(e.g. Fisher and Hochbaum (8) and Papadimitriou(22). On the other hand,

the literature on the k-median problem abounds in exact algorithms. Most are

based on the solution of a certain relaxation to be defined later. The computational

experience reported in the literature seems to indicate that this particular

relaxation yields impressively tight bounds compared to what can usually be

expected in integer programming. In this paper we analyze to what extent

this relaxation is tight. We perform our analysis for a classical Euclidean model

in the plane and show that the relaxation can be expected to provide a bound

within one third of one percent of the optimum value of the k-median problem.