◈ 학술지
◈ 도서
◈ 전자학술지
◈ 투고요령
◈ 수학신간도서
◈ MSC
◈ 논문검색
◈ 학술행사
홈 > 학술정보 >학술행사 > 세미나
KAIST Discrete Math 세미나

Title
New algorithm for multiway cut guided by strong min-max duality
Speaker
Eun Jung Kim   (CNRS, LAMSADE, Paris, France )
Date
2019-01-04 16:00:00
Host
Place
Room B232, DIMAG, IBS
Abstract
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. In 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 4^(k-μ(I)) for multiway cut and its generalizations, where k is the budget for a solution. This talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.
개인정보보호정책 l 이메일주소집단수집금지 l 뷰어다운로드
qr코드