{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:25:27Z","timestamp":1778495127537,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T00:00:00Z","timestamp":1670630400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T00:00:00Z","timestamp":1670630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["459\/20"],"award-info":[{"award-number":["459\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,5]]},"DOI":"10.1007\/s00453-022-01071-2","type":"journal-article","created":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T20:02:10Z","timestamp":1670702530000},"page":"1332-1371","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Practical Budgeted Submodular Maximization"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elad","family":"Shoham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,10]]},"reference":[{"key":"1071_CR1","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: SODA, pp. 1497\u20131514 (2014)","DOI":"10.1137\/1.9781611973402.110"},{"issue":"6","key":"1071_CR2","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011). https:\/\/doi.org\/10.1137\/080733991","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1071_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ipl.2008.03.017","volume":"108","author":"R Cohen","year":"2008","unstructured":"Cohen, R., Katzir, L.: The generalized maximum coverage problem. Inf. Process. Lett. 108(1), 15\u201322 (2008)","journal-title":"Inf. Process. Lett."},{"key":"1071_CR4","doi-asserted-by":"crossref","unstructured":"De, A., Koley, P., Ganguly, N., Gomez-Rodriguez, M.: Regression under human assistance. In: AAAI, pp. 2611\u20132620 (2020). https:\/\/aaai.org\/ojs\/index.php\/AAAI\/article\/view\/5645","DOI":"10.1609\/aaai.v34i03.5645"},{"key":"1071_CR5","unstructured":"Elenberg, E.R., Dimakis, A.G., Feldman, M., Karbasi, A.: Streaming weak submodularity: Interpreting neural networks on the fly. In: NeurIPS, pp. 4047\u20134057 (2017)"},{"key":"1071_CR6","unstructured":"Ene, A., Nguyen, H.L.: A nearly-linear time algorithm for submodular maximization with a knapsack constraint. ICALP, pp. 53:1\u201353:12 (2019)"},{"key":"1071_CR7","doi-asserted-by":"publisher","unstructured":"Feldman, M., Naor, J., Schwartz, R., Ward, J.: Improved approximations for k-exchange systems - (extended abstract). In: Demetrescu, C., Halld\u00f3rsson, M.M. (Eds.) ESA Lecture notes in computer science vol. 6942, pp. 784\u2013798. Springer, Berlin (2011). https:\/\/doi.org\/10.1007\/978-3-642-23719-5_66","DOI":"10.1007\/978-3-642-23719-5_66"},{"key":"1071_CR8","doi-asserted-by":"crossref","unstructured":"Feldman, M., Nutov, Z., Shoham, E.: Practical budgeted submodular maximization. CoRR arxiv:2007.04937 (2021)","DOI":"10.1007\/s00453-022-01071-2"},{"issue":"2","key":"1071_CR9","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Y Filmus","year":"2014","unstructured":"Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514\u2013542 (2014). https:\/\/doi.org\/10.1137\/130920277","journal-title":"SIAM J. Comput."},{"key":"1071_CR10","unstructured":"Kazemi, E., Zadimoghaddam, M., Karbasi, A.: Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. In: ICML, pp. 2549\u20132558 (2018)"},{"key":"1071_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inform. Process. Lett. 70, 39\u201345 (1999)","journal-title":"Inform. Process. Lett."},{"key":"1071_CR12","unstructured":"Kulik, A., Schwartz, R., Shachnai, H.: A faster tight approximation for submodular maximization subject to a knapsack constraint. CoRR arxiv:2102.12879 (2021)"},{"issue":"4","key":"1071_CR13","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1287\/moor.2013.0592","volume":"38","author":"A Kulik","year":"2013","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4), 729\u2013739 (2013). https:\/\/doi.org\/10.1287\/moor.2013.0592","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1071_CR14","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795\u2013806 (2010). https:\/\/doi.org\/10.1287\/moor.1100.0463","journal-title":"Math. Oper. Res."},{"key":"1071_CR15","unstructured":"Lei, Q., Wu, L., Chen, P., Dimakis, A., Dhillon, I.S., Witbrock, M.J.: Discrete adversarial attacks and submodular optimization with applications to text classification. In: MLSys, pp. 146\u2013165 (2019). https:\/\/proceedings.mlsys.org\/book\/284.pdf"},{"issue":"4","key":"1071_CR16","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1002\/prot.25461","volume":"86","author":"MW Libbrecht","year":"2018","unstructured":"Libbrecht, M.W., Bilmes, J.A., Noble, W.S.: Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization. Proteins: Struct., Funct., and Bioinfor. 86(4), 454\u2013466 (2018)","journal-title":"Proteins: Struct., Funct., and Bioinfor."},{"key":"1071_CR17","first-page":"238:1","volume":"17","author":"B Mirzasoleiman","year":"2016","unstructured":"Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization. J. Mach. Learn. Res. 17, 238:1-238:44 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"1071_CR18","unstructured":"Mitrovic, M., Morteza Zadimoghaddam, E.K., Karbasi, A.: Data summarization at scale: a two-stage submodular approach. In: ICML, pp. 3593\u20133602 (2018)"},{"issue":"3","key":"1071_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177\u2013188 (1978). https:\/\/doi.org\/10.1287\/moor.3.3.177","journal-title":"Math. Oper. Res."},{"key":"1071_CR20","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. Programm. 14, 265\u2013294 (1978)","journal-title":"Math. Programm."},{"key":"1071_CR21","doi-asserted-by":"crossref","unstructured":"Salehi, M., Karbasi, A., Scheinost, D., Constable, R.T.: A submodular approach to create individualized parcellations of the human brain. In: MICCAI, pp. 478\u2013485 (2017)","DOI":"10.1007\/978-3-319-66182-7_55"},{"key":"1071_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Operat. Res. Lett. 32, 41\u201343 (2004)","journal-title":"Operat. Res. Lett."},{"issue":"1","key":"1071_CR23","doi-asserted-by":"publisher","first-page":"08:1","DOI":"10.1145\/3447386","volume":"5","author":"J Tang","year":"2021","unstructured":"Tang, J., Tang, X., Lim, A., Han, K., Li, C., Yuan, J.: Revisiting modified greedy algorithm for monotone submodular maximization with a knapsack constraint. Proc. ACM Meas. Anal. Comput. Syst. 5(1), 08:1-08:22 (2021). https:\/\/doi.org\/10.1145\/3447386","journal-title":"Proc. ACM Meas. Anal. Comput. Syst."},{"key":"1071_CR24","doi-asserted-by":"publisher","unstructured":"Ward, J.: A $$(k+3)\/2$$-approximation algorithm for monotone submodular k-set packing and general k-exchange systems. In: C.\u00a0D\u00fcrr, T.\u00a0Wilke (eds.) STACS, LIPIcs, vol.\u00a014, pp. 42\u201353. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2012). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.42","DOI":"10.4230\/LIPIcs.STACS.2012.42"},{"key":"1071_CR25","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, 410\u2013425 (1982)","journal-title":"Math. Oper. Res."},{"key":"1071_CR26","unstructured":"Yaroslavtsev, G., Zhou, S., Avdiukhin, D.: \u201cBring your own greedy\u201d+max: Near-optimal 1\/2-approximations for submodular knapsack. In: AISTATS, pp. 3263\u20133274 (2020)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01071-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01071-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01071-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,25]],"date-time":"2023-04-25T00:03:04Z","timestamp":1682380984000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01071-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,10]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1071"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01071-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,10]]},"assertion":[{"value":"5 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}