Optimal Set Partitioning
F. K. Hwang, Jie Sun, E. Y. Yao · SIAM Journal on Algebraic and Discrete Methods · 1985
We consider the problem of partitioning a set of elements into unlabeled subsets to minimize cost, where the cost of a partition is essentially the sum of costs contributed by the component subsets. We give several results which specify conditions on the cost functions such that there always exists an optimal partition which is an “ordered partition” (an optimal ordered partition can be determined in quadratic time). We also give several applications to illustrate the usefulness of our results.