Research on the approximated algorithms for k-Median problem has been a focus of computer scientists, and most of the existing results are based on the Euclidean and Metric k-Median problem. However, results for general distance space k-Median has not been 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 shortest edge for one client point. In this paper, it is first proved that there are no polynomial algorithms of approximation ratio 1+ω-1/e for k-Median with the condition d_max/d_min≤ω+ε, unless NP=DTIME(n^{O (loglog n)}) . This result implies there are no polynomial algorithms of approximation ratio 1+2/e for Metric k-Median unless NP=DTIME(n^O(loglogn)). Then a local search algorithm for k-Median is presented. New analysis shows that the local search can achieve a ratio of 1+ω-1/2. This result can also be extended to the Metric k-Median, and if ω≤5, the local search algorithm can achieve a ratio less than 3 for the Metric k-Median, which is better than the existing best ratio 3+2/p. Finally, p computer verification is used to study the real computational effect and the improved method of the local search algorithm.