{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:04Z","timestamp":1780783144568,"version":"3.54.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_26","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:29Z","timestamp":1780780469000},"page":"370-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hardness of\u00a0SetCover Reoptimization"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8358-6796","authenticated-orcid":false,"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2509-6972","authenticated-orcid":false,"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-2448-4794","authenticated-orcid":false,"given":"Bj\u00f6rn","family":"Schumacher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"issue":"2","key":"26_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for K-Restrictions. ACM Trans. Algorithms 2(2), 153\u2013177 (2006). https:\/\/doi.org\/10.1145\/1150334.1150336","journal-title":"ACM Trans. Algorithms"},{"key":"26_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-540-93980-1_16","volume-title":"Approximation and Online Algorithms","author":"D Bil\u00f2","year":"2009","unstructured":"Bil\u00f2, D., Widmayer, P., Zych, A.: Reoptimization of weighted graph and covering problems. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 201\u2013213. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-93980-1_16"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H-J B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 50\u201365. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-77566-9_5"},{"issue":"3","key":"26_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/MOOR.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979). https:\/\/doi.org\/10.1287\/MOOR.4.3.233","journal-title":"Math. Oper. Res."},{"key":"26_CR5","doi-asserted-by":"publisher","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Shmoys, D.B., Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 624\u2013633. ACM (2014). https:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"issue":"4","key":"26_CR6","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-Parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995). https:\/\/doi.org\/10.1137\/S0097539792228228","journal-title":"SIAM J. Comput."},{"key":"26_CR7","doi-asserted-by":"publisher","unstructured":"Fundamentals of Parameterized Complexity. TCS, Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1_35","DOI":"10.1007\/978-1-4471-5559-1_35"},{"issue":"4","key":"26_CR8","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998). https:\/\/doi.org\/10.1145\/285055.285059","journal-title":"J. ACM"},{"key":"26_CR9","doi-asserted-by":"publisher","unstructured":"Parameterized Complexity Theory. TTCSAES, Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X","DOI":"10.1007\/3-540-29953-X"},{"issue":"3","key":"26_CR10","doi-asserted-by":"publisher","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(3), 256\u2013278 (1974). https:\/\/doi.org\/10.1016\/S0022-0000(74)80044-9","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"26_CR11","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discret. Math. 13(4), 383\u2013390 (1975). https:\/\/doi.org\/10.1016\/0012-365X(75)90058-8","journal-title":"Discret. Math."},{"issue":"5","key":"26_CR12","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/185675.306789","journal-title":"J. ACM"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/11847250_14","volume-title":"Parameterized and Exact Computation","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 154\u2013165. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11847250_14"},{"issue":"6","key":"26_CR14","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1007\/s10559-010-9269-z","volume":"46","author":"V Mikhailyuk","year":"2010","unstructured":"Mikhailyuk, V.: Reoptimization of set covering problems. Cybern. Syst. Anal. 46(6), 879\u2013883 (2010)","journal-title":"Cybern. Syst. Anal."},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/11671411_23","volume-title":"Approximation and Online Algorithms","author":"T Nieberg","year":"2006","unstructured":"Nieberg, T., Hurink, J.: A PTAS for the minimum dominating set problem in unit disk graphs. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 296\u2013306. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11671411_23"},{"issue":"2","key":"26_CR16","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/S00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W -hard problems hard: FPT algorithms for W -hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008). https:\/\/doi.org\/10.1007\/S00453-007-9148-9","journal-title":"Algorithmica"},{"key":"26_CR17","doi-asserted-by":"publisher","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Leighton, F.T., Shor, P.W., Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4\u20136, 1997, pp. 475\u2013484. ACM (1997). https:\/\/doi.org\/10.1145\/258533.258641","DOI":"10.1145\/258533.258641"},{"issue":"2","key":"26_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/JAGM.1997.0887","volume":"25","author":"P Slav\u00edk","year":"1997","unstructured":"Slav\u00edk, P.: A tight analysis of the greedy algorithm for set cover. J. Algorithms 25(2), 237\u2013254 (1997). https:\/\/doi.org\/10.1006\/JAGM.1997.0887","journal-title":"J. Algorithms"},{"key":"26_CR19","doi-asserted-by":"publisher","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. STOC \u201901, pp. 453\u2013461. Association for Computing Machinery, Hersonissos, Greece (2001). https:\/\/doi.org\/10.1145\/380752.380839","DOI":"10.1145\/380752.380839"},{"key":"26_CR20","doi-asserted-by":"publisher","unstructured":"Zych, A.: Reoptimization of NP-hard Problems, ETH Zurich, Z\u00fcrich, Switzerland. PhD thesis (2012). https:\/\/doi.org\/10.3929\/ETHZ-A-007161496","DOI":"10.3929\/ETHZ-A-007161496"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:29Z","timestamp":1780780469000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}