Seminars

View all Seminars  |  Download ICal for this event

Partitioning over Submodular Structures – Part I

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 17 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 survey some recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constants k>=3. As a main technical result, I will present a random contraction algorithm for min-cut in hypergraphs �?? this is a generalization of Kargers algorithm for min-cut in graphs.
<br>
<br>
Microsoft Teams Link:
<br>
<a href="Link
">Link
<br>
<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Anand Louis