Parameterized (in)approximability of subset problems |
| |
Affiliation: | PSL* Research University, Université Paris-Dauphine, LAMSADE, CNRS UMR 7243, France |
| |
Abstract: | ![]() We discuss approximability and inapproximability in FPT-time for a large class of subset problems where a feasible solution is a subset of the input data. We introduce the notion of intersective approximability that generalizes the one of safe approximability introduced in Guo et al. (2011) and show strong parameterized inapproximability results for many of the subset problems handled. |
| |
Keywords: | Approximation Complexity Graph Parameterized algorithm |
本文献已被 ScienceDirect 等数据库收录! |