Algorithms
(Jun 2020)
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Andreas Emil Feldmann,
Karthik C. S.,
Euiwoong Lee,
Pasin Manurangsi
Affiliations
Andreas Emil Feldmann
Department of Applied Mathematics (KAM), Charles University, 118 00 Prague, Czech Republic
Karthik C. S.
Department of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel
Euiwoong Lee
Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA
Pasin Manurangsi
Google Research, Mountain View, CA 94043, USA
DOI
https://doi.org/10.3390/a13060146
Journal volume & issue
Vol. 13,
no. 6
p.
146
Abstract
Read online
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.
Keywords
Published in Algorithms
ISSN
1999-4893 (Online)
Publisher
MDPI AG
Country of publisher
Switzerland
LCC subjects
Technology: Technology (General): Industrial engineering. Management engineering
Science: Mathematics: Instruments and machines: Electronic computers. Computer science
Website
https://www.mdpi.com/journal/algorithms
About the journal
WeChat QR code
Close