We learn from our alumni in this interaction series, often technically, sometimes semi-technically.

Karthekeyan Chandrasekaran Department of Industrial and Enterprise Systems Engineering UIUC

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.

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