{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T18:23:56Z","timestamp":1765045436901},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,5,20]],"date-time":"2014-05-20T00:00:00Z","timestamp":1400544000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s00453-014-9889-1","type":"journal-article","created":{"date-parts":[[2014,5,19]],"date-time":"2014-05-19T16:56:36Z","timestamp":1400518596000},"page":"541-565","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["On Subexponential and FPT-Time Inapproximability"],"prefix":"10.1007","volume":"71","author":[{"given":"Edouard","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Bruno","family":"Escoffier","sequence":"additional","affiliation":[]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,20]]},"reference":[{"issue":"3","key":"9889_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"9889_CR2","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9889_CR3","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.orl.2014.03.005","volume":"42","author":"E Bonnet","year":"2014","unstructured":"Bonnet, E., Paschos, VTh: Parameterized (in)approximability of subset problems. Oper. Res. Lett. 42(3), 222\u2013225 (2014)","journal-title":"Oper. Res. Lett."},{"issue":"16","key":"9889_CR4","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1016\/j.ipl.2009.05.002","volume":"109","author":"N Bourgeois","year":"2009","unstructured":"Bourgeois, N., Escoffier, B., Paschos, VTh: Efficient approximation of min coloring by moderately exponential algorithms. Inf. Process. Lett. 109(16), 950\u2013954 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"17","key":"9889_CR5","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., Paschos, VTh: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159(17), 1954\u20131970 (2011)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"9889_CR6","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On fixed-parameter tractability and approximability of np optimization problems. J. Comput. Syst. Sci. 54(3), 465\u2013474 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9889_CR7","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/s00453-008-9223-x","volume":"57","author":"L Cai","year":"2010","unstructured":"Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. Algorithmica 57(2), 398\u2013412 (2010)","journal-title":"Algorithmica"},{"key":"9889_CR8","unstructured":"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)"},{"issue":"8","key":"9889_CR9","doi-asserted-by":"crossref","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9889_CR10","first-page":"106","volume":"14","author":"V Chen","year":"2007","unstructured":"Chen, V., Grohe, M., Gr\u00fcber, M.: On parameterized approximability. Electron. Colloq. Comput. Complex. 14, 106 (2007)","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"9889_CR11","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Hajiaghayi, M., Kortsarz, G.: Fixed-parameter and approximation algorithms: a new look. CoRR, abs\/1308.3520, (2013)","DOI":"10.1007\/978-3-319-03898-8_11"},{"issue":"40\u201342","key":"9889_CR12","doi-asserted-by":"crossref","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40\u201342), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9889_CR13","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007). Article 12","journal-title":"J. ACM"},{"key":"9889_CR14","series-title":"Monographs in computer science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in computer science. Springer, New York (1999)"},{"key":"9889_CR15","doi-asserted-by":"crossref","unstructured":"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\u201906, volume 4169 of Lecture Notes in Computer Science. Springer-Verlag, 121\u2013129 (2006)","DOI":"10.1007\/11847250_11"},{"issue":"1","key":"9889_CR16","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","volume":"109","author":"RG Downey","year":"2008","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C., Rosamond, F.A.: Parameterized approximation of dominating set problems. Inf. Process. Lett. 109(1), 68\u201370 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9889_CR17","unstructured":"Escoffier, B., Paschos, V.Th., Tourniaire, E.: Moderately exponential and parameterized approximation: some structural results. Unpublished manuscript."},{"key":"9889_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2013.03.024","volume":"511","author":"M F\u00fcrer","year":"2013","unstructured":"F\u00fcrer, M., Gaspers, S., Kasiviswanathan, S.P.: An exponential time 2-approximation algorithm for bandwidth. Theor. Comput. Sci. 511, 23\u201331 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9889_CR19","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O Gabber","year":"1981","unstructured":"Gabber, O., Galil, Z.: Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22(3), 407\u2013420 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"9889_CR20","series-title":"A guide to the theory of NP-completeness","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979)"},{"key":"9889_CR21","doi-asserted-by":"crossref","unstructured":"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\u201911, volume 7112 of Lecture Notes in Computer Science. Springer-Verlag, 169\u2013180 (2011)","DOI":"10.1007\/978-3-642-28050-4_14"},{"key":"9889_CR22","unstructured":"Hajiaghayi, M., Khandekar, R., Kortsarz, G.: The foundations of fixed parameter inapproximability. CoRR, abs\/1310.2711, (2013)"},{"issue":"4","key":"9889_CR23","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. AMS 43(4), 439\u2013561 (2006)","journal-title":"Bull. AMS"},{"issue":"4","key":"9889_CR24","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9889_CR25","doi-asserted-by":"crossref","unstructured":"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\u201911, volume 7112 of Lecture Notes in Computer Science. Springer-Verlag, 118\u2013131 (2011)","DOI":"10.1007\/978-3-642-28050-4_10"},{"issue":"4","key":"9889_CR26","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"LL Cai","year":"2003","unstructured":"Cai, L.L., Juedes, D.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67(4), 789\u2013807 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9889_CR27","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"9889_CR28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0190(96)00031-2","volume":"58","author":"MV Marathe","year":"1996","unstructured":"Marathe, M.V., Ravi, S.S.: On approximation algorithms for the minimum satisfiability problem. Inf. Process. Lett. 58(1), 23\u201329 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9889_CR29","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"key":"9889_CR30","unstructured":"Mathieson, L.: A proof checking view of parameterized complexity. CoRR, abs\/1206.2436, (2012)"},{"issue":"5","key":"9889_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1754399.1754402","volume":"57","author":"D Moshkovitz","year":"2008","unstructured":"Moshkovitz, D., Raz, R.: Two-query pcp with subconstant error. J. ACM 57(5), 1\u201329 (2008)","journal-title":"J. ACM"},{"key":"9889_CR32","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9889_CR33","unstructured":"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)"},{"issue":"2","key":"9889_CR34","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"HU Simon","year":"1990","unstructured":"Simon, H.U.: On approximate solutions for combinatorial optimization problems. SIAM J. Discret. Math. 3(2), 294\u2013310 (1990)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"9889_CR35","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(6), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9889-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9889-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9889-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T16:02:19Z","timestamp":1565452939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9889-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,20]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["9889"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9889-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,20]]}}}