An asymptotically exact polynomial algorithm for equipartition problems

We describe an approximate algorithm for a special ‘quadratic semi-assignment problem’ arising from ‘equipartition’ applications, where one wants to cluster n objects with given weights w_i into p classes, so as to minimize the variance of the class-weights. The algorithm can be viewed both as a list scheduling method and as a special case of a heuristic procedure, due to Nemhauser and Carlson, for quadratic semi-assignment problems. Our main result is that the relative approximation error is O(1/n) when p and r = (maxw_i)/(min w_i) are bounded.