Submodular Cost Allocation Problem and Applications

We study the Minimum Submodular-Cost Allocation problem (MSCA). In this problem we are given a finite ground set V and k non-negative submodular set functions f(1), ..., f(k) on V. The objective is to partition V into k (possibly empty) sets A(1), ..., A(k) such that the sum Sigma(k)(i=1) f(i) (A(i)) is minimized. Several well-studied problems such as the non-metric facility location problem, multiway-cut in graphs and hypergraphs, and uniform metric labeling and its generalizations can be shown to be special cases of MSCA. In this paper we consider a convex-programming relaxation obtained via the Lovasz-extension for submodular functions. This allows us to understand several previous relaxations and rounding procedures in a unified fashion and also develop new formulations and approximation algorithms for related problems. In particular, we give a (1.5 - 1/k)-approximation for the hypergraph multiway partition problem. We also give a min{2(1 - 1/k), H-Delta}-approximation for the hypergraph multiway cut problem when Delta is the maximum hyperedge size. Both problems generalize the multiway cut problem in graphs and the hypergraph cut problem is approximation equivalent to the node-weighted multiway cut problem in graphs.