  \textit{Clustering problems} often arise in the fields like data mining,
machine learning etc. to group a collection of objects into similar groups with
respect to a similarity (or dissimilarity) measure. Among the clustering
problems, specifically \textit{$k$-means} clustering has got much attention
from the researchers. Despite the fact that $k$-means is a very well studied
problem its status in the plane is still an open problem. In particular, it is
unknown whether it admits a PTAS in the plane. The best known approximation
bound in polynomial time is $9+\eps$.
  In this paper, we consider the following variant of $k$-means. Given a set
$C$ of points in $\mathcal{R}^d$ and a real $f > 0$, find a finite set $F$ of
points in $\mathcal{R}^d$ that minimizes the quantity $f*|F|+\sum_{p\in C}
\min_{q \in F} {||p-q||}^2$. For any fixed dimension $d$, we design a local
search PTAS for this problem. We also give a "bi-criterion" local search
algorithm for $k$-means which uses $(1+\eps)k$ centers and yields a solution
whose cost is at most $(1+\eps)$ times the cost of an optimal $k$-means
solution. The algorithm runs in polynomial time for any fixed dimension.
  The contribution of this paper is two fold. On the one hand, we are being
able to handle the square of distances in an elegant manner, which yields near
optimal approximation bound. This leads us towards a better understanding of
the $k$-means problem. On the other hand, our analysis of local search might
also be useful for other geometric problems. This is important considering that
very little is known about the local search method for geometric approximation.
