A Probabilistic Analysis of a relaxation for the K-median Problem -A Graphical Model

Abstract

This paper is sequal to the paper(l), where we performed probabilistic analysis

for the Euclidean k-median problem in the plane. In this paper, our

analysis is concerned with the following graphical k-median problem Let G; (p) be a random graph with n nodes, where each edge occurs independently with probability p, and C;j is the minimum number of edges on a

path joining i to j for where the minimum is taken over all paths joining i to i. Thus C;j is the shortest distance between i and j, assuming that all edges have length one.