文章基本信息

标题：A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
本地全文：下载
作者：Andreas Feldmann ; Karthik C. S. ; Euiwoong Lee 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-73
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.