BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20220317T120000Z
UID:fa31a5c3e06cbd1302ba5516aa9da194-258
DTSTAMP:19700101T120021Z
DESCRIPTION:Partitioning over Submodular Structures – Part I
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/258/partitioning-over-submodular-structures-ae-part-i/
SUMMARY: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="https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
">https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d</a>
<br>
<br> 
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
DTSTART:20220317T120000Z
END:VEVENT
END:VCALENDAR