Research on randomized greedy algorithm for k-median problem

This paper presented a randomized greedy algorithm for k-median problem. First some facilities were drawn at random from the given facility set. Among these sample facilities, there exist k facilities to satisfy that the approximation ratio is at most 3 with high probability, if used to serve the whole given clients. Then, a (3+O ((β-1)In(In(k)/α)))-approximation algorithm was given for this problem. At last, some datasets were used to test the valid of the greedy algorithm.