{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:41Z","timestamp":1781077601225,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P26696"],"award-info":[{"award-number":["P26696"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","award":["BEHARD"],"award-info":[{"award-number":["BEHARD"]}],"id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992, 715744, 267959"],"award-info":[{"award-number":["306992, 715744, 267959"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055456","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"224-237","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Lossy kernelization"],"prefix":"10.1145","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"Vienna University of Technology, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway \/ Institute of Mathematical Sciences, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90072-H"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_3_2_2_5_1","volume-title":"Cross-Composition: A New Technique for Kernelization Lower Bounds. In 28th International Symposium on \ue049eoretical Aspects of Computer Science (STACS). 165\u2013 176","author":"Bodlaender Hans L.","year":"2011","unstructured":"Hans L. Bodlaender , Bart M. P. Jansen , and Stefan Kratsch . 2011 . Cross-Composition: A New Technique for Kernelization Lower Bounds. In 28th International Symposium on \ue049eoretical Aspects of Computer Science (STACS). 165\u2013 176 . Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. 2011. Cross-Composition: A New Technique for Kernelization Lower Bounds. In 28th International Symposium on \ue049eoretical Aspects of Computer Science (STACS). 165\u2013 176."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_3_2_2_9_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095122"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"key":"e_1_3_2_2_12_1","volume-title":"On the hardness of approximating minimum vertex cover. Annals of mathematics","author":"Dinur Irit","year":"2005","unstructured":"Irit Dinur and Samuel Safra . 2005. On the hardness of approximating minimum vertex cover. Annals of mathematics ( 2005 ), 439\u2013485. Irit Dinur and Samuel Safra. 2005. On the hardness of approximating minimum vertex cover. Annals of mathematics (2005), 439\u2013485."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"e_1_3_2_2_14_1","volume-title":"Parameterized complexity","author":"Downey Rodney G","unstructured":"Rodney G Downey and Michael Ralph Fellows . 2012. Parameterized complexity . Springer Science & amp; Business Media. Rodney G Downey and Michael Ralph Fellows. 2012. Parameterized complexity. Springer Science & Business Media."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"e_1_3_2_2_17_1","volume-title":"Sophia Antipolis","author":"Fellows Michael R.","year":"2013","unstructured":"Michael R. Fellows , Danny Hermelin , Frances A. Rosamond , and Hadas Shachnai . 2013 . Tractable Parameterizations for the Minimum Linear Arrangement Problem. In Algorithms - ESA 2013 - 21st Annual European Symposium , Sophia Antipolis , France , September 2-4, 2013. Proceedings. 457\u2013468. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Hadas Shachnai. 2013. Tractable Parameterizations for the Minimum Linear Arrangement Problem. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings. 457\u2013468."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_30"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118782.3119219"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9910-8"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095125"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523689"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_2_27_1","volume-title":"Recent developments in kernelization: A survey. Bulletin of the EATCS 113","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch . 2014. Recent developments in kernelization: A survey. Bulletin of the EATCS 113 ( 2014 ). Stefan Kratsch. 2014. Recent developments in kernelization: A survey. Bulletin of the EATCS 113 (2014)."},{"key":"e_1_3_2_2_28_1","volume-title":"Kernelization\u2013 preprocessing with a guarantee. In \ue049e Multivariate Algorithmic Revolution and Beyond","author":"Lokshtanov Daniel","unstructured":"Daniel Lokshtanov , Neeldhara Misra , and Saket Saurabh . 2012. Kernelization\u2013 preprocessing with a guarantee. In \ue049e Multivariate Algorithmic Revolution and Beyond . Springer , 129\u2013161. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Kernelization\u2013 preprocessing with a guarantee. In \ue049e Multivariate Algorithmic Revolution and Beyond. Springer, 129\u2013161."},{"key":"e_1_3_2_2_29_1","volume-title":"CoRR abs\/1604.04111","author":"Lokshtanov Daniel","year":"2016","unstructured":"Daniel Lokshtanov , Fahad Panolan , M. S. Ramanujan , and Saket Saurabh . 2016. Lossy Kernelization . CoRR abs\/1604.04111 ( 2016 ). http:\/\/arxiv.org\/abs\/1604. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. 2016. Lossy Kernelization. CoRR abs\/1604.04111 (2016). http:\/\/arxiv.org\/abs\/1604."},{"key":"e_1_3_2_2_30_1","unstructured":"04111  04111"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"e_1_3_2_2_32_1","volume-title":"\ue049e Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. \ue049eory of Computing 11","author":"Moshkovitz Dana","year":"2015","unstructured":"Dana Moshkovitz . 2015. \ue049e Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. \ue049eory of Computing 11 ( 2015 ), 221\u2013235. Dana Moshkovitz. 2015. \ue049e Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. \ue049eory of Computing 11 (2015), 221\u2013235."},{"key":"e_1_3_2_2_33_1","volume-title":"A Note on Set Cover Inapproximability Independent of Universe Size. Electronic Colloquium on Computational Complexity (ECCC) 14, 105","author":"Nelson Jelani","year":"2007","unstructured":"Jelani Nelson . 2007. A Note on Set Cover Inapproximability Independent of Universe Size. Electronic Colloquium on Computational Complexity (ECCC) 14, 105 ( 2007 ). Jelani Nelson. 2007. A Note on Set Cover Inapproximability Independent of Universe Size. Electronic Colloquium on Computational Complexity (ECCC) 14, 105 (2007)."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496915_5"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90022-9"},{"key":"e_1_3_2_2_36_1","unstructured":"Michael Sipser. 2012. Introduction to the \ue049eory of Computation. Cengage Learning.  Michael Sipser. 2012. Introduction to the \ue049eory of Computation. Cengage Learning."},{"key":"e_1_3_2_2_37_1","volume-title":"Shmoys","author":"Williamson David P.","year":"2011","unstructured":"David P. Williamson and David B . Shmoys . 2011 . \ue049e Design of Approximation Algorithms. Cambridge University Press . David P. Williamson and David B. Shmoys. 2011. \ue049e Design of Approximation Algorithms. Cambridge University Press."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055456","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055456","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055456"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":37,"alternative-id":["10.1145\/3055399.3055456","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055456","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}