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:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190104T160000
DTEND;TZID=Asia/Seoul:20190104T170000
DTSTAMP:20260423T191547
CREATED:20181217T143613Z
LAST-MODIFIED:20240705T211439Z
UID:279-1546617600-1546621200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, New algorithm for multiway cut guided by strong min-max duality
DESCRIPTION:Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then\, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design. \nIn this talk\, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds\, namely μ(I)=2LP(I)-IP(dual-I). Here\, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result\, we obtain an algorithm running in time 4k-μ(I) for multiway cut and its generalizations\, where k is the budget for a solution. \nThis talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.
URL:https://dimag.ibs.re.kr/event/2019-01-04/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR