The research on approximated algorithms for k-Median problem is a focus of computer scientists all along, and most existed results are based on Euclidean and Metric k-Median problem, however, results for General distance space k-Median is not found for many years. In General distance space, let dmax/dmin denote the maximum value of the length of the longest edge divided by the length of the ortest edge for one client point. In this paper, we first prove that there are no polynomial algorithms of approximation ratio 1+e1−ωk-Median with condition dmax/dmin≤ω+ε, unlessDTIMNP⊆result implies there are no polynomial algorithms of approximation ratio 1+2elog (lognone2 for Metric k-Median unless. Then a local search algorithm for k-Median is presented. New analysis shows that local search can achieve a ratio of