In this paper we present an approximation algorithm for (k,m) optimal partition problem on an undirected graph. We show that this approximation algorithm which produces a near optimal solution runs in polynomial time. The performance ratio in the worst case is bounded by a parameter k, which is independent of input size of the problem.