Before revision:  All our algorithms run in near linear time in the number of points and the dimension .
After revision:  Given an approximate solution to the classic k-means and k-medians, our algorithm for k-medians runs in time O(kd \log^2 k ) and our algorithm for k-means runs in time O(k^2 d) .