K-Median Problem on Graph

Abstract

In past decades there has been a tremendous growth in the

literature on location problems. However, among the myriad of

formulations provided, the simple plant location problem and

the k-median problem have played a central role. This

phenomenon is due to the fact that both problems have a wide

range of real-world applications, and a mathematical

formulation of these problems as an integer program has proven

very fruitful in the derivation of solution methods.

In this paper we investigate the k-median problem defined on

a graph. That is, each point represents a vertex of a graph.