{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:47:18Z","timestamp":1759063638886},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,12]],"date-time":"2016-10-12T00:00:00Z","timestamp":1476230400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00236-016-0281-2","type":"journal-article","created":{"date-parts":[[2016,10,12]],"date-time":"2016-10-12T15:34:26Z","timestamp":1476286466000},"page":"1-15","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sparsification and subexponential approximation"],"prefix":"10.1007","volume":"55","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,12]]},"reference":[{"key":"281_CR1","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s00037-011-0027-z","volume":"20","author":"M Alekhnovich","year":"2011","unstructured":"Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong nonapproximability results in the Lov\u00e1sz-Schrijver hierarchy. Comput. Complex. 20, 615\u2013648 (2011)","journal-title":"Comput. Complex."},{"key":"281_CR2","first-page":"399","volume-title":"Approximation Algorithms for NP-Hard Problems, Chapter\u00a010","author":"S Arora","year":"1997","unstructured":"Arora, S., Lund, C.: Hardness of approximation. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, Chapter\u00a010, pp. 399\u2013446. PWS, Boston (1997)"},{"issue":"3","key":"281_CR3","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. Assoc. Comput. Mach. 45(3), 501\u2013555 (1998)","journal-title":"J. Assoc. Comput. Mach."},{"key":"281_CR4","volume-title":"Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin (1999)"},{"key":"281_CR5","doi-asserted-by":"crossref","unstructured":"Bonnet, E., Escoffier, B., Kim, E., Paschos, V.Th: On subexponential and FPT-time inapproximability. Algorithmica 71(3), 541\u2013565 (2015)","DOI":"10.1007\/s00453-014-9889-1"},{"key":"281_CR6","unstructured":"Bonnet, E., Paschos, V.Th.: Sparsification and subexponential approximation. CoRR (2014). \n                        arXiv:1402.2843"},{"key":"281_CR7","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.Th.: Efficient approximation by \u201clow-complexity\u201d exponential algorithms. Cahier du LAMSADE 271, LAMSADE, Universit\u00e9 Paris-Dauphine (2007). \n                        http:\/\/www.lamsade.dauphine.fr\/cahiers\/PDF\/cahierLamsade271"},{"issue":"17","key":"281_CR8","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. Discrete Appl. Math. 159(17), 1954\u20131970 (2011)","journal-title":"Discrete Appl. Math."},{"key":"281_CR9","doi-asserted-by":"crossref","unstructured":"Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC\u201906, volume 4169 of Lecture Notes in Computer Science, pp. 96\u2013108. Springer-Verlag (2006)","DOI":"10.1007\/11847250_9"},{"key":"281_CR10","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In: IEEE Symposium on Foundations of Computer Science, FOCS\u201913, pp. 370\u2013379 (2013)","DOI":"10.1109\/FOCS.2013.47"},{"key":"281_CR11","unstructured":"Chen, Y., Grohe, M., Gr\u00fcber, M.: On parameterized approximability. Electron. Colloq. Comput. Complex. 14(106) (2007)"},{"issue":"40\u201342","key":"281_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."},{"key":"281_CR13","doi-asserted-by":"crossref","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J.\u00a0Assoc. Comput. Mach. 54(3) (2007) (Article 12)","DOI":"10.1145\/1236457.1236459"},{"key":"281_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R. G., Fellows, M. R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H. L., Langston, M. A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC\u201906, volume 4169 of Lecture Notes in Computer Science, pp. 121\u2013129. Springer-Verlag, NY (2006)","DOI":"10.1007\/11847250_11"},{"key":"281_CR15","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."},{"key":"281_CR16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"MM Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: Approximating the minimum maximal independence number. Inform. Process. Lett. 46, 169\u2013172 (1993)","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"281_CR17","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":"281_CR18","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"RW Irving","year":"1991","unstructured":"Irving, R.W.: On approximating the minimum independent dominating set. Inform. Process. Lett. 37, 197\u2013200 (1991)","journal-title":"Inform. Process. Lett."},{"key":"281_CR19","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"281_CR20","unstructured":"Johnson, D.S., Szegedy, M.: What are the least tractable instances of max independent set? In: Proc. Symposium on Discrete Algorithms, SODA\u201999, pp. 927\u2013928 (1999)"},{"key":"281_CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"281_CR22","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"1","key":"281_CR23","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. Inform. Process. Lett. 58(1), 23\u201329 (1996)","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"281_CR24","first-page":"29:1","volume":"57","author":"D Moshkovitz","year":"2008","unstructured":"Moshkovitz, D., Raz, R.: Two-query PCP with subconstant error. J. ACM 57(5), 29:1\u201329:29 (2008)","journal-title":"J. ACM"},{"key":"281_CR25","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)"},{"key":"281_CR26","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."},{"issue":"2","key":"281_CR27","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. Disc. Math. 3(2), 294\u2013310 (1990)","journal-title":"SIAM J. Disc. Math."},{"issue":"6","key":"281_CR28","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":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-016-0281-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0281-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0281-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,2,1]],"date-time":"2018-02-01T13:26:25Z","timestamp":1517491585000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-016-0281-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,12]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["281"],"URL":"https:\/\/doi.org\/10.1007\/s00236-016-0281-2","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,12]]}}}