Completely Inapproximable Monotone and Antimonotone Parameterized Problems
Dániel Marx · 2010
We prove that weighted monotone/antimonotone circuit satisfiability has no fixed-parameter tractable approximation algorithm with any approximation ratio function ρ, unless FPT ≠ W[1]. In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio ρ(OPT) for any nontrivial function ρ.