Room 327

Partitioning over Submodular Structures

Chandrasekaran, Karthik

UIUC

In submodular k-partitioning problems, the input is a submodular set function (given via an evaluation oracle) along with a fixed positive integer k (e.g., k = 2, 3, 4, …) and the goal is to partition the ground set into k non-empty parts so as to minimize certain natural objectives of interest. Submodular k-partitioning generalizes partitioning problems over several interesting structures including graphs and hypergraphs. The case of 2-partitioning corresponds to the classic and well-studied submodular minimization problem which is polynomial-time solvable. In this talk, I will outline recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constants k >= 3. As one of the technical results, I will present a random contraction algorithm for min-cut in “hypergraphs” that generalizes the well-known Karger’s algorithm for min-cut in graphs.