Given an undirected graph \(G=(V,E)\) , the minimum k-star partition problem is to find a collection of vertex-disjoint stars containing at most k vertices to cover all the vertices of V. The objective is to minimize the number of stars in the collection. In this paper, we give a local search algorithm which achieves an approximation ratio of \(\frac{k}{2}-\frac{k-2}{k(k+1)}\) when \(k\ge 5\) is even and \(\frac{k}{2}-\frac{k-2}{2k^2}\) when \(k\ge 5\) is odd. This improves on the previous best \(\frac{k}{2}\) -approximation algorithm implied by Hell and Kirkpatrick for each \(k\ge 5\) . In addition, we give examples to show that our analysis is tight.