[2017 Discrete Math 세미나 ]

** Date: ** 2017-07-06

**Speaker :** 이의웅 (Computer Science Department, Carnegie Mellon Univesity)

**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-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

**VOD : **[Android_VOD] [iPhone_VOD] [Windows_VOD]

Information Center for Mathematical Sciences KAIST

305-701 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8195~6 / 팩스 042-350-5722

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2017. ICMS All Rights Reserved.

305-701 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8195~6 / 팩스 042-350-5722

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2017. ICMS All Rights Reserved.