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.