Completely inapproximable monotone and antimonotone parameterized problems

被引：14

作者：

Marx, Daniel ^{[1
]}

机构：

[1] Hungarian Acad Sci MTA SZTAKI, Comp & Automat Res Inst, Budapest, Hungary

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2013年 / 79卷 / 01期

基金：

欧洲研究理事会;

关键词：

Inapproximability; Fixed-parameter tractability; Circuits; Circuit satisfiability; APPROXIMATION; APPROXIMABILITY;

D O I：

10.1016/j.jcss.2012.09.001

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We prove that weighted circuit satisfiability for monotone or antimonotone circuits has no fixed-parameter tractable approximation algorithm with any approximation ratio function rho, unless FPT not equal W[1]. In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio rho(OPT) for any nontrivial function rho. (C) 2012 Elsevier Inc. All rights reserved.

引用

页码：144 / 151

页数：8

共 17 条

[1] RESOLUTION IS NOT AUTOMATIZABLE UNLESS W[P] IS TRACTABLE
Alekhnovich, Michael
Razborov, Alexander A.
[J]. SIAM JOURNAL ON COMPUTING, 2008, 38 (04) : 1347 - 1363
[2] COLOR-CODING
ALON, N
YUSTER, R
ZWICK, U
[J]. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (04): : 844 - 856
[3] Bousquet N, 2011, ACM S THEORY COMPUT, P459
[4] Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
Cai, Liming
Huang, Xiuzhen
[J]. ALGORITHMICA, 2010, 57 (02) : 398 - 412
[5] Chen YJ, 2006, LECT NOTES COMPUT SC, V4169, P109
[6] Downey RG, 2006, LECT NOTES COMPUT SC, V4169, P121
[7] Parameterized approximation of dominating set problems
Downey, Rodney G.
Fellows, Michael R.
McCartin, Catherine
Rosamond, Frances
[J]. INFORMATION PROCESSING LETTERS, 2008, 109 (01) : 68 - 70
[8] Approximation of natural W[P]-complete minimisation problems is hard
Eickmeyer, Kord
Grohe, Martin
Grueber, Magdalena
[J]. TWENTY-THIRD ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2008, : 8 - 18
[9] Improved approximation algorithms for minimum weight vertex separators
Feige, Uriel
Hajiaghayi, Mohammadtaghi
Lee, James R.
[J]. SIAM JOURNAL ON COMPUTING, 2008, 38 (02) : 629 - 657
[10] On the parameterized complexity of multiple-interval graph problems
Fellows, Michael R.
Hermelin, Danny
Rosamond, Frances
Vialette, Stephane
[J]. THEORETICAL COMPUTER SCIENCE, 2009, 410 (01) : 53 - 61

← 1 2 →