Tytuł: Parameterized Inapproximability
Prelegent: Pasin Manurangsi
Czas i miejsce: wtorek, 25-go czerwca 2019, 10:15, sala 310
Streszczenie: The area of parameterized complexity seeks a more fine-grained understanding of NP-hard problems by relaxing the notion of efficient algorithms to the so-called fixed-parameter tractability (FPT). After more than two decades of work, the parameterized complexity of many fundamental problems have been classified; that is, each problem is either shown to be in FPT or shown to be hard for some complexity class that is believed to not be in FPT. However, for most problems not in FPT, their approximability statuses remain open. Specifically, there were few techniques to prove hardness of approximation in the parameterized regime. This has somewhat changed in the last few years where more tools have been developed to tackle such problems. In this talk, I will survey some these recent developments and interesting questions that remain open.
