On Subexponential and FPT-Time Inapproximability

详细信息    查看全文

• 作者：Edouard Bonnet (1)
  Bruno Escoffier (2) (3)
  Eun Jung Kim (1)
  Vangelis Th. Paschos (1) (4)
  
  1. PSL Research University ; Universit茅 Paris-Dauphine ; LAMSADE ; CNRS UMR 7243 ; Paris ; France
  2. Sorbonne Universit茅s ; UPMC Universit茅 Paris 06 ; UMR 7606 ; LIP6 ; 75005 ; 聽Paris ; France
  3. CNRS ; UMR 7606 ; LIP6 ; 75005 ; 聽Paris ; France
  4. Institut Universitaire de France ; Paris ; France
  
• 关键词：Inapproximability ; Subexponential time ; FPT ; time ; APETH
• 刊名：Algorithmica
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：71
• 期：3
• 页码：541-565
• 全文大小：288 KB
• 参考文献：1. Arora, S, Lund, C, Motwani, R, Sudan, M, Szegedy, M (1998) Proof verification and intractability of approximation problems. J. ACM 45: pp. 501-555 CrossRef
  2. Bj枚rklund, A, Husfeldt, T, Koivisto, M (2009) Set partitioning via inclusion-exclusion. SIAM J. Comput. 39: pp. 546-563 CrossRef
  3. Bonnet, E, Paschos, VTh (2014) Parameterized (in)approximability of subset problems. Oper. Res. Lett. 42: pp. 222-225 2014.03.005" target="_blank" title="It opens in new window">CrossRef
  4. Bourgeois, N, Escoffier, B, Paschos, VTh (2009) Efficient approximation of min coloring by moderately exponential algorithms. Inf. Process. Lett. 109: pp. 950-954 2009.05.002" target="_blank" title="It opens in new window">CrossRef
  5. Bourgeois, N, Escoffier, B, Paschos, VTh (2011) Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159: pp. 1954-1970
  6. Cai, L, Chen, J (1997) On fixed-parameter tractability and approximability of np optimization problems. J. Comput. Syst. Sci. 54: pp. 465-474 CrossRef
  7. Cai, L, Huang, X (2010) Fixed-parameter approximation: conceptual framework and approximability results. Algorithmica 57: pp. 398-412 CrossRef
  8. Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. CoRR, abs/1308.2617, abs/1308.2617, (2013)
  9. Chen, J, Huang, X, Kanj, IA, Xia, G (2006) Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72: pp. 1346-1367 2006.04.007" target="_blank" title="It opens in new window">CrossRef
  10. Chen, V, Grohe, M, Gr眉ber, M (2007) On parameterized approximability. Electron. Colloq. Comput. Complex. 14: pp. 106
  11. Chitnis, R.H., Hajiaghayi, M., Kortsarz, G.: Fixed-parameter and approximation algorithms: a new look. CoRR, abs/1308.3520, (2013)
  12. Cygan, M, Pilipczuk, M (2010) Exact and approximate bandwidth. Theor. Comput. Sci. 411: pp. 3701-3713 2010.06.018" target="_blank" title="It opens in new window">CrossRef
  13. Dinur, I (2007) The PCP theorem by gap amplification. J. ACM 54: pp. 12 CrossRef
  14. Downey, RG, Fellows, MR (1999) Parameterized complexity. Springer, New York CrossRef
  15. Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In H. L. Bodlaender and M. A. Langston, editors, Proc. International Workshop on Parameterized and Exact Computation, IWPEC鈥?6, volume 4169 of Lecture Notes in Computer Science. Springer-Verlag, 121鈥?29 (2006)
  16. Downey, RG, Fellows, MR, McCartin, C, Rosamond, FA (2008) Parameterized approximation of dominating set problems. Inf. Process. Lett. 109: pp. 68-70 2008.09.017" target="_blank" title="It opens in new window">CrossRef
  17. Escoffier, B., Paschos, V.Th., Tourniaire, E.: Moderately exponential and parameterized approximation: some structural results. Unpublished manuscript.
  18. F眉rer, M, Gaspers, S, Kasiviswanathan, SP (2013) An exponential time 2-approximation algorithm for bandwidth. Theor. Comput. Sci. 511: pp. 23-31 2013.03.024" target="_blank" title="It opens in new window">CrossRef
  19. Gabber, O, Galil, Z (1981) Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22: pp. 407-420 CrossRef
  20. Garey, MR, Johnson, DS (1979) Computers and intractability. W. H. Freeman, San Francisco
  21. Guo, J., Kanj, I., Kratsch, S.: Safe approximation and its relation to kernelization. In D. Marx and P. Rossmanith, editors, Proc. International Workshop on Parameterized and Exact Computation, IPEC鈥?1, volume 7112 of Lecture Notes in Computer Science. Springer-Verlag, 169鈥?80 (2011)
  22. Hajiaghayi, M., Khandekar, R., Kortsarz, G.: The foundations of fixed parameter inapproximability. CoRR, abs/1310.2711, (2013)
  23. Hoory, S, Linial, N, Wigderson, A (2006) Expander graphs and their applications. Bull. AMS 43: pp. 439-561 CrossRef
  24. Impagliazzo, R, Paturi, R, Zane, F (2001) Which problems have strongly exponential complexity?. J. Comput. Syst. Sci. 63: pp. 512-530 2001.1774" target="_blank" title="It opens in new window">CrossRef
  25. Kim, E.J., Williams, R.: Improved parameterized algorithms for above average constraint satisfaction. In D. Marx and P. Rossmanith, editors, Proc. International Symposium on Parameterized and Exact Computation, IPEC鈥?1, volume 7112 of Lecture Notes in Computer Science. Springer-Verlag, 118鈥?31 (2011)
  26. Cai, LL, Juedes, D (2003) On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67: pp. 789-807 CrossRef
  27. Lund, C, Yannakakis, M (1994) On the hardness of approximating minimization problems. J. ACM 41: pp. 960-981 CrossRef
  28. Marathe, MV, Ravi, SS (1996) On approximation algorithms for the minimum satisfiability problem. Inf. Process. Lett. 58: pp. 23-29 20-0190(96)00031-2" target="_blank" title="It opens in new window">CrossRef
  29. Marx, D (2008) Parameterized complexity and approximation algorithms. Comput. J. 51: pp. 60-78 CrossRef
  30. Mathieson, L.: A proof checking view of parameterized complexity. CoRR, abs/1206.2436, (2012)
  31. Moshkovitz, D, Raz, R (2008) Two-query pcp with subconstant error. J. ACM 57: pp. 1-29 CrossRef
  32. Papadimitriou, CH, Yannakakis, M (1991) Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43: pp. 425-440 CrossRef
  33. Reingold, O., Vadhan, S.P., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. Electron. Colloq. Comput. Complex., 8(18), (2001)
  34. Simon, HU (1990) On approximate solutions for combinatorial optimization problems. SIAM J. Discret. Math. 3: pp. 294-310 CrossRef
  35. Zuckerman, D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3: pp. 103-128 2007.v003a006" target="_blank" title="It opens in new window">CrossRef
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithm design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once endowed with subexponential-time or FPT-time is a central question. In this article, we provide new insights to this question using two complementary approaches; the former makes a strong link between the linear PCP conjecture and inapproximability; the latter builds a class of equivalent problems under approximation in subexponential time.