Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
The submodular system k-partition problem is a problem of partitioning a given finite set V into k non-empty subsets V (1),V (2),aEuro broken vertical bar,V (k) so that E-i=1(k) f(V-i) is minimized where f is a non-negative submodular function on V. In this paper, we design an approximation algorithm for the problem with fixed k. We also analyze the approximation factor of our algorithm for the hypergraph k-cut problem, which is a problem contained by the submodular system k-partition problem.
divide-and-conquer algorithm hypergraph submodular function multicut