We consider coresets for k-median problems, where the goal is to assign points to centers minimizing the sum of distances. Given a point set P, a coreset Ω is a small weighted subset that approximates the cost of P for all candidate solutions up to a (1 ± ε) multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for k-median coreset construction. As a consequence, we obtain improved k-median coreset bounds for the following metrics: