| Title | : | Partitioning over Submodular Structures |
| Speaker | : | Karthekeyan Chandrasekaran (2007 B.Tech CSE Alumnus) (Univ of Illinois, Urbana Champaign) |
| Details | : | Thu, 23 Feb, 2023 3:30 PM @ CS15 |
| Abstract: | : | 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 in order 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. |
