BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210727T150000
DTEND;TZID=Asia/Seoul:20210727T160000
DTSTAMP:20260426T000014
CREATED:20210623T055635Z
LAST-MODIFIED:20240707T081214Z
UID:4288-1627398000-1627401600@dimag.ibs.re.kr
SUMMARY:Euiwoong Lee (이의웅)\, The Karger-Stein algorithm is optimal for k-cut
DESCRIPTION:In the k-cut problem\, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with the running time of $O(n^{2k-2})$. Using tree packings\, Thorup gave a deterministic algorithm that has the same running time. \nIn this work\, we show that for any fixed $k\ge 2$\, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least $\Omega(n^{-k})$. This also gives an extremal bound of $O(n^k)$ on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are essentially tight. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta)OPT/k$\, using the Sunflower lemma. \nJoint work with Anupam Gupta\, David G. Harris\, and Jason Li.
URL:https://dimag.ibs.re.kr/event/2021-07-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR