Speaker:

Bingkai Lin(Nanjing University)

Time:

• 10:00-11:00 (Time in Beijing)
• April 20, 2021 (Tuesday)

VooVmeeting:

ZOOM ID: 467 156 1455

Password: 图灵机被提出的年份（4位）

Bilibili Live:

http://live.bilibili.com/22528138

Abstract:

Deciding whether a graph contains a k‍‍-Clique is a well-known NP‍‍-hard problem.
One approach to dealing with NP‍‍-hard problem is approximation algorithm. However, assuming NP \ne P ‍‍,
no polynomial time algorithm can approximate k‍‍-Clique to any factor within n^{1-\epsilon}‍‍. Another approach
is FPT‍‍-algorithm, i.e. algorithm with running time upper bounded by f(k)poly(n) ‍‍ for some computable
function f‍‍. Unfortunately, assuming W[1] \ne FPT‍‍, the k‍‍-Clique problem has no FPT‍‍-algorithm.
A natural question is: Is there any FPT‍‍-algorithm that can approximate k‍‍-Clique to 1-\epsilon‍‍?
We give a negative answer to this question under the assumption that k‍‍-Clique problem has no FPT‍‍-algorithm.

Speaker Bio:

Bingkai Lin is a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University. Prior to joining Nanjing University, he was a researcher at National Institute of Informatics. He obtained his PhD degree at the University of Tokyo in 2016. He received his Master and Bachelor’s degree at Shanghai Jiao Tong University in 2013 and 2010 respectively. His primary research interests are parameterized complexity and algorithms.