DocumentCode :
2834096
Title :
Completely Inapproximable Monotone and Antimonotone Parameterized Problems
Author :
Marx, Dániel
Author_Institution :
Tel Aviv Univ., Tel Aviv, Israel
fYear :
2010
fDate :
9-12 June 2010
Firstpage :
181
Lastpage :
187
Abstract :
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 ρ.
Keywords :
approximation theory; circuit complexity; computability; approximation ratio function; inapproximable antimonotone parameterized problems; inapproximable monotone parameterized problems; nontrivial function; weighted monotone-antimonotone circuit satisfiability; Approximation algorithms; Circuits; Computational complexity; Cost function; Minimization methods; Optimized production technology; Polynomials; Turning; approximation; fixed-parameter tractability; inapproximability; parameterized comlexity;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
Conference_Location :
Cambridge, MA
ISSN :
1093-0159
Print_ISBN :
978-1-4244-7214-7
Electronic_ISBN :
1093-0159
Type :
conf
DOI :
10.1109/CCC.2010.25
Filename :
5497888
Link To Document :
بازگشت