We prove that weighted circuit satisfiability for monotone or antimonotone circuits has no fixed-parameter tractable approximation algorithm with any approximation ratio function ρ, unless . In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio for any nontrivial function ρ.
IEEE Annual Conference on Computational Complexity (CCC)
2010-06-01
2026-06-08