AN APPROXIMATION ALGORITHM ON GRAPH (K,M) OPTIMAL PARTITION PROBLEM
图(k,m)最优划分的近似算法

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.