首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Parameterized (in)approximability of subset problems
Institution: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 S 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号