In submodular k-partitioning problems, the input is a submodular function (via an evaluation oracle) 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 some recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constants k>=3.
Based on joint works with Chao Xu, Xilin Yu, and Chandra Chekuri.
Karthekeyan Chandrasekaran is an assistant professor in Industrial and Enterprise Systems Engineering and an affiliate assistant professor in Computer Science at the University of Illinois, Urbana-Champaign (UIUC). He received his Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Georgia Tech. Prior to joining UIUC, he was a Simons Postdoctoral Fellow in the Theory of Computation group at Harvard University. His research interests are in combinatorial optimization, design and analysis of algorithms, and integer programming.
Zoom Registration → Register for full spring series.