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

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2834096