## Alum @ AlmaCSE IIT MadrasWe learn from our alumni in this interaction series, often technically, sometimes semi-technically.
Karthekeyan Chandrasekaran is a faculty member at the Department of Industrial and Enterprise Systems Engineering and an affiliate at the Department of Computer Science at the University of Illinois, Urbana-Champaign. He completed BTech from our department in 2007 and PhD from Georgia Tech. His research interests are in Combinatorial Optimization, Algorithms, Math Programming, Probabilistic Methods, etc.
Partitioning over Submodular Structures
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.
## Organizers |