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

Title
FPT Approximation Algorithms for Graph Problems
Speaker
이의웅   (Computer Science Department, Carnegie Mellon University )
Date
2017-07-06 16:00:00
Host
KAIST
Place
E6-1 Room 1409
Abstract
Approximation algorithms and fixed-parameter tractable (FPT) algorithms have been two major ways to deal with NP-hardness of combinatorial optimization problems. The notion of FPT approximation can be naturally defined, and it is getting significant attention recently. Starting from gentle introductions to approximation algorithms and FPT algorithms, I will talk about my three recent results on FPT approximability. – Given a graph G = (V, E) and an integer k, we study k-Vertex Separator, where the goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most k vertices. We give an O(log k)-FPT approximation algorithm for k-Vertex Separator. Our result improves the best previous graph partitioning algorithms. – We also study k-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. We present an O(log k)-FPT approximation algorithm for k-Path Transversal. There was no nontrivial approximation algorithm for k > 4 before this work. – Finally, k-cut is the problem where we want to remove the minimum number of edges such that the graph has at least k connected components. We give a (2 – ε)-FPT approximation algorithm for some epsilon > 0, improving upon a (non-FPT) 2-approximation. The third result is joint work with Anupam Gupta and Jason Li.
개인정보보호정책 l 이메일주소집단수집금지 l 뷰어다운로드
qr코드