Maurice Queyranne

On optimum size-constrained set partitions


Given a set N with n elements, a function f associating a cost f(S) to each subset S of N, and integers h and k, we consider the problem of finding a partition of N into at least h and at most k nonempty parts S1,..,Sm, with minimum total cost f(S1)+...+ f(Sm). Such problems arise in VLSI design (netlist partitioning), clustering, network flows, and graph connectivity. In the oracle model, the function f is only known through a value oracle, which returns the cost f(S) for any proposed subset S. Thus we assume no information on *how* f(S) is computed. Without further assumptions on f, the problem requires an exponential number of oracle calls to find (or even to approximate) an optimum partition. When the cost function f is submodular, we identify important cases that can be solved to optimality in polynomial time in this oracle model. When f is also symmetric (every subset has the same cost as its complement, as happens with network and hypergraph cuts), optimum partitions can be found in polynomial time for any fixed h and k. Because the solution time grows very rapidly with h and k, we also present a simple approximation algorithm with performance guarantee better than two. This algorithm is purely combinatorial and uses O(n^4) oracle calls. Its analysis relies on the existence of cut trees (aka Gomory-Hu trees) for symmetric submodular set functions. Some of the results presented in this talk extend to (symmetric) submodular functions results obtained for network cut functions by Nagamochi and Ibaraki; Baiou, Barahona and Mahjoub; Goldschmidt and Hochbaum; Gomory and Hu; and Saran and Vazirani.

Maurice Queyranne
address: Faculty of Commerce and Business Administration, University of British Columbia, 2053 Main Mall, Vancouver, B.C., Canada V6T 1Z2