Finding k Cuts within Twice the Optimal

Two simple approximation algorithms for the minimum k-cut problem are presented. Each algorithm finds a k cut having weight within a factor of $(2 - 2/k)$ of the optimal. One algorithm is particularly efficient—it requires a total of only $n - 1$ maximum flow computations for finding a set of near-optimal k cuts, one for each value of k between 2 and n.