Abstract: Research on the approximated algorithms for k-median problem has been a focus of computer scientists.Based on the balanced parameter, this paper presented a randomized algorithm for k-median problem by means of the reverse greedy. The new algorithm's expected approximate ratio was proved to be(3}0(ln(ln(k)/a)) with high probability. The running time of the new algorithm is巨立ln(k)习z(二+二)，wher。二。nd yn represent the number of clients and facilities for the given instance. Finally,computer verification was used to study the real computational effect of the al gorithm.

Key words: k- median, Randomized algorithm, Reverse greedy, Aapproximation ratio