{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T16:17:43Z","timestamp":1783700263148,"version":"3.55.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T00:00:00Z","timestamp":1783641600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T00:00:00Z","timestamp":1783641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018755","name":"Universit\u00e4t Trier","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018755","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,9]]},"abstract":"Abstract<\/jats:title>\n \n We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classic problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution\u2019s cardinality. If any deleted elements were part of the initial solution, they are replaced with a set of at most equal cardinality. The objective is to maximize the value of the ultimate solution, with the deletion being maximally disadvantageous to the ultimate solution. When the submodular function is\n \n \n $${{\\,\\mathrm{ \\text {M}^\\natural }\\,}}$$<\/jats:tex-math>\n \n \n \n \n M<\/mml:mtext>\n \u266e<\/mml:mo>\n <\/mml:msup>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -concave, we prove that a simple greedy algorithm computes an optimal solution. When only one element may be deleted, we propose a polynomial running time algorithm with an approximation factor of at least\n \n \n $$\\frac{1}{3}$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . When the number of deletions may become as large as the cardinality parameter, we present a polynomial running time algorithm that approximates an optimal ultimate solution in dependence on the curvature of the submodular function. Furthermore, assuming that the number of allowed deletions is upper bounded by a term of the order of\n \n \n $$\\frac{k}{\\log _2^2(k)}$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \n \n log<\/mml:mo>\n 2<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , where\n k<\/jats:italic>\n is the cardinality parameter, we adapt an algorithm from Bogunovic et al.\u00a0and show that its approximation factor is at least 0.108.\n <\/jats:p>","DOI":"10.1007\/s00236-026-00542-1","type":"journal-article","created":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T15:48:45Z","timestamp":1783698525000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Recoverable robust cardinality constrained maximization with commitment of a submodular function"],"prefix":"10.1007","volume":"63","author":[{"given":"Sabine","family":"M\u00fcnch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Raach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"de Vries","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,10]]},"reference":[{"key":"542_CR1","doi-asserted-by":"publisher","unstructured":"Ageev, A.A.,Sviridenko, M.I.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discret. Appl. Math. 93(2\u20133), 149\u2013156 (1999). https:\/\/doi.org\/10.1016\/S0166-218X(99)00103-1","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"542_CR2","doi-asserted-by":"publisher","unstructured":"Bing, M., Lehmann, D., Milgrom, P.: Presentation and structure of substitutes valuations. In: Proceedings of the 5th ACM Conference on Electronic Commerce, EC \u201904, pp. 238\u2013239. Association for Computing Machinery (2004). https:\/\/doi.org\/10.1145\/988772.988812","DOI":"10.1145\/988772.988812"},{"key":"542_CR3","unstructured":"Bogunovic, I., Mitrovi\u0107, S., Scarlett, J., Cevher, V.: Robust submodular maximization: a non-uniform partitioning approach. In: Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 70, pp. 508\u2013516. PMLR (2017)"},{"key":"542_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.dam.2022.02.005","volume":"313","author":"M Bold","year":"2022","unstructured":"Bold, M., Goerigk, M.: Investigating the recoverable robust single machine scheduling problem under interval uncertainty. Discret. Appl. Math. 313, 99\u2013114 (2022). https:\/\/doi.org\/10.1016\/j.dam.2022.02.005","journal-title":"Discret. Appl. Math."},{"key":"542_CR5","doi-asserted-by":"publisher","unstructured":"B\u00fcsing, C., Koster, A.M.C.A., Kutschka, M.: Recoverable robust knapsacks: $$\\Gamma $$-scenarios. In: Proceedings of INOC 2011, International Network Optimization Conference, Lecture Notes in Computer Science, vol. 6701, pp. 583\u2013588. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-21527-8_65","DOI":"10.1007\/978-3-642-21527-8_65"},{"key":"542_CR6","volume-title":"Recoverable Robustness in Combinatorial Optimization","author":"C B\u00fcsing","year":"2011","unstructured":"B\u00fcsing, C.: Recoverable Robustness in Combinatorial Optimization. Cuvillier Verlag (2011)"},{"key":"542_CR7","doi-asserted-by":"publisher","unstructured":"B\u00fcsing, C., Koster, A.M.C.A., Kutschka, M.: Recoverable robust knapsacks: the discrete scenario case. Opt. Lett. 5, 379\u2013392 (2011). https:\/\/doi.org\/10.1007\/s11590-011-0307-1","DOI":"10.1007\/s11590-011-0307-1"},{"key":"542_CR8","doi-asserted-by":"publisher","unstructured":"B\u00fcsing, C., Goderbauer, S., Koster, A.M.C.A., Kutschka, M.: Formulations and algorithms for the recoverable $$\\Gamma $$-robust knapsack problem. EURO J. Comput. Opt. 7(1), 15\u201345 (2019). https:\/\/doi.org\/10.1007\/s13675-018-0107-9","DOI":"10.1007\/s13675-018-0107-9"},{"issue":"3","key":"542_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"G Cornuejols","year":"1984","unstructured":"Cornuejols, G., Conforti, M.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discret. Appl. Math. 7(3), 251\u2013274 (1984). https:\/\/doi.org\/10.1016\/0166-218X(84)90003-9","journal-title":"Discret. Appl. Math."},{"issue":"8","key":"542_CR10","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G Cornuejols","year":"1977","unstructured":"Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Exceptional paper\u2014location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789\u2013810 (1977). https:\/\/doi.org\/10.1287\/mnsc.23.8.789","journal-title":"Manag. Sci."},{"issue":"3","key":"542_CR11","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1002\/net.21624","volume":"66","author":"MC Dourado","year":"2015","unstructured":"Dourado, M.C., Meierling, D., Penso, L.D., Rautenbach, D., Protti, F., de Almeida, A.R.: Robust recoverable perfect matchings. Network 66(3), 210\u2013213 (2015). https:\/\/doi.org\/10.1002\/net.21624","journal-title":"Network"},{"key":"542_CR12","doi-asserted-by":"publisher","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: improving the factor of 1-1\/e. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), pp. 667\u2013676. IEEE (2006). https:\/\/doi.org\/10.1109\/FOCS.2006.14","DOI":"10.1109\/FOCS.2006.14"},{"key":"542_CR13","doi-asserted-by":"publisher","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","DOI":"10.1145\/285055.285059"},{"key":"542_CR14","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA \u201906, pp. 611\u2013620. Society for Industrial and Applied Mathematics (2006)","DOI":"10.1145\/1109557.1109624"},{"key":"542_CR15","doi-asserted-by":"publisher","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995). https:\/\/doi.org\/10.1145\/227683.227684","DOI":"10.1145\/227683.227684"},{"issue":"2","key":"542_CR16","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/j.ejor.2022.03.001","volume":"303","author":"M Goerigk","year":"2022","unstructured":"Goerigk, M., Lendl, S., Wulf, L.: Recoverable robust representatives selection problems with discrete budgeted uncertainty. Eur. J. Oper. Res. 303(2), 567\u2013580 (2022). https:\/\/doi.org\/10.1016\/j.ejor.2022.03.001","journal-title":"Eur. J. Oper. Res."},{"key":"542_CR17","doi-asserted-by":"publisher","unstructured":"Hommelsheim, F., Megow, N., Muluk, K., Peis, B.: Recoverable robust optimization with commitment. https:\/\/doi.org\/10.48550\/arXiv.2306.08546. Preprint arXiv:2306.08546 (2023)","DOI":"10.48550\/arXiv.2306.08546"},{"key":"542_CR18","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/s10878-016-0089-6","volume":"34","author":"M Hradovich","year":"2017","unstructured":"Hradovich, M., Kasperski, A., Zieli\u0144ski, P.: Recoverable robust spanning tree problem under interval uncertainty representations. J. Comb. Optim. 34, 554\u2013573 (2017). https:\/\/doi.org\/10.1007\/s10878-016-0089-6","journal-title":"J. Comb. Optim."},{"key":"542_CR19","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s11590-016-1057-x","volume":"11","author":"M Hradovich","year":"2017","unstructured":"Hradovich, M., Kasperski, A., Zieli\u0144ski, P.: The recoverable robust spanning tree problem with interval costs is polynomially solvable. Opt. Lett. 11, 17\u201330 (2017). https:\/\/doi.org\/10.1007\/s11590-016-1057-x","journal-title":"Opt. Lett."},{"issue":"1","key":"542_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1002\/net.22255","volume":"85","author":"M Jackiewicz","year":"2024","unstructured":"Jackiewicz, M., Kasperski, A., Zieli\u0144ski, P.: Recoverable robust shortest path problem under interval budgeted uncertainty representations. Networks 85(1), 127\u2013141 (2024). https:\/\/doi.org\/10.1002\/net.22255","journal-title":"Networks"},{"issue":"4","key":"542_CR21","doi-asserted-by":"publisher","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","volume":"11","author":"D Kempe","year":"2015","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. Theory Comput. 11(4), 105\u2013147 (2015). https:\/\/doi.org\/10.4086\/toc.2015.v011a004","journal-title":"Theory Comput."},{"key":"542_CR22","unstructured":"Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In: Proceedings of the 22nd National Conference on Artificial Intelligence, AAAI\u201907, vol. 2, pp. 1650\u20131654 (2007)"},{"issue":"93","key":"542_CR23","first-page":"2761","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., McMahan, H.B., Guestrin, C., Gupta, A.: Robust submodular observation selection. J. Mach. Learn. Res. 9(93), 2761\u20132801 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"542_CR24","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.dam.2020.08.012","volume":"303","author":"T Lachmann","year":"2021","unstructured":"Lachmann, T., Lendl, S., Woeginger, G.J.: A linear time algorithm for the robust recoverable selection problem. Discret. Appl. Math. 303, 94\u2013107 (2021). https:\/\/doi.org\/10.1016\/j.dam.2020.08.012","journal-title":"Discret. Appl. Math."},{"key":"542_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-05465-5_1","volume-title":"The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications","author":"C Liebchen","year":"2009","unstructured":"Liebchen, C., L\u00fcbbecke, M., M\u00f6hring, R., Stiller, S.: The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications, pp. 1\u201327. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-05465-5_1"},{"key":"542_CR26","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, HLT \u201911, vol. 1, pp. 510\u2013520. Springer, Cham (2011)"},{"key":"542_CR27","doi-asserted-by":"publisher","unstructured":"M\u00fcnch, S., Raach, S., de\u00a0Vries, S.: Recoverable robust cardinality constrained maximization with commitment of a submodular function. In: Combinatorial Algorithms. IWOCA 2025, Lecture Notes in Computer Science, vol. 15885, pp. 376\u2013390. Springer (2025). https:\/\/doi.org\/10.1007\/978-3-031-98740-3_27","DOI":"10.1007\/978-3-031-98740-3_27"},{"key":"542_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics (2003). https:\/\/doi.org\/10.1137\/1.9780898718508"},{"key":"542_CR29","doi-asserted-by":"publisher","unstructured":"Murota, K.: Multiple exchange property for $$\\text{M}^\\natural $$-concave functions and valuated matroids. Math. Oper. Res. 43(3), 781\u2013788 (2018). https:\/\/doi.org\/10.1287\/moor.2017.0882","DOI":"10.1287\/moor.2017.0882"},{"issue":"1","key":"542_CR30","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s13160-017-0285-5","volume":"35","author":"K Murota","year":"2018","unstructured":"Murota, K., Shioura, A.: Simpler exchange axioms for M-concave functions on generalized polymatroids. Jpn. J. Ind. Appl. Math. 35(1), 235\u2013259 (2018). https:\/\/doi.org\/10.1007\/s13160-017-0285-5","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"542_CR31","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14, 265\u2013294 (1978). https:\/\/doi.org\/10.1007\/BF01588971","journal-title":"Math. Program."},{"key":"542_CR32","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s10107-018-1320-2","volume":"172","author":"JB Orlin","year":"2018","unstructured":"Orlin, J.B., Schulz, A.S., Udwani, R.: Robust monotone submodular function maximization. Math. Program. 172, 505\u2013537 (2018). https:\/\/doi.org\/10.1007\/s10107-018-1320-2","journal-title":"Math. Program."},{"key":"542_CR33","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/j.geb.2017.10.016","volume":"106","author":"R Paes Leme","year":"2017","unstructured":"Paes Leme, R.: Gross substitutability: an algorithmic survey. Games Econ. Behav. 106, 294\u2013316 (2017). https:\/\/doi.org\/10.1016\/j.geb.2017.10.016","journal-title":"Games Econ. Behav."},{"key":"542_CR34","unstructured":"Tschiatschek, S., Iyer, R., Wei, H., Bilmes, J.: Learning mixtures of submodular functions for image collection summarization. In: Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS\u201914, vol. 1, pp. 1413\u20131421 (2014)"},{"key":"542_CR35","unstructured":"Wei, K., Iyer, R., Bilmes, J.: Submodularity in data subset selection and active learning. In: Proceedings of the 32nd International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 37, pp. 1954\u20131963. PMLR (2015)"},{"issue":"3","key":"542_CR36","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res. 7(3), 410\u2013425 (1982). https:\/\/doi.org\/10.1287\/moor.7.3.410","journal-title":"Math. Oper. Res."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00542-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-026-00542-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00542-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T15:48:54Z","timestamp":1783698534000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-026-00542-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,10]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["542"],"URL":"https:\/\/doi.org\/10.1007\/s00236-026-00542-1","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,10]]},"assertion":[{"value":"16 October 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"26"}}