Seminars
View all Seminars | Download ICal for this eventPartitioning over Submodular Structures – Part II
Series: Theory Seminar
Speaker: Prof. Karthekeyan Chandrasekaran, Associate Professor, Department of Industrial and Enterprise Systems Engineering, Affiliate, Department of Computer Science, University of Illinois, Urbana-Cham
Date/Time: Mar 24 21:00:00
Location: Microsoft Teams - ON-LINE
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 present a polynomial time algorithm for minmax symmetric submodular k-partitioning for every fixed k.
Microsoft Teams Link:
Link
For more details about the seminar please visit the website at Link
Host Faculty: Dr. Anand Louis