{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:55:05Z","timestamp":1761648905012,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T00:00:00Z","timestamp":1626048000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T00:00:00Z","timestamp":1626048000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["497\/14"],"award-info":[{"award-number":["497\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"publisher","award":["3-10996"],"award-info":[{"award-number":["3-10996"]}],"id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003023","name":"Minist\u00e8re de l\u2019\u00c9ducation Nationale","doi-asserted-by":"publisher","award":["31768XL"],"award-info":[{"award-number":["31768XL"]}],"id":[{"id":"10.13039\/501100003023","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["NeTOC"],"award-info":[{"award-number":["NeTOC"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00453-021-00850-7","type":"journal-article","created":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T11:03:13Z","timestamp":1626087793000},"page":"2989-3014","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Budgeted Maximum Coverage"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0323-6097","authenticated-orcid":false,"given":"Dror","family":"Rawitz","sequence":"first","affiliation":[]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,12]]},"reference":[{"issue":"3","key":"850_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307\u2013328 (2004)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"850_CR2","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput. 39(2), 361\u2013370 (2009)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"850_CR3","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)","journal-title":"ACM Trans. Algorithms"},{"issue":"13\u201314","key":"850_CR4","doi-asserted-by":"publisher","first-page":"1901","DOI":"10.1016\/j.dam.2012.04.005","volume":"160","author":"G Ausiello","year":"2012","unstructured":"Ausiello, G., Boria, N., Giannakos, A., Lucarelli, G., Paschos, V.T.: Online maximum $$k$$-coverage. Discret. Appl. Math. 160(13\u201314), 1901\u20131913 (2012)","journal-title":"Discret. Appl. Math."},{"key":"850_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Fiat, A., Leighton, F.T.: Making commitments in the face of uncertainty: how to pick a winner almost every time. In: 28th Annual ACM Symposium on the Theory of Computing, pp. 519\u2013530 (1996)","DOI":"10.1145\/237814.238000"},{"key":"850_CR6","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A.: Buyback problem\u2014approximate matroid intersection with cancellation costs. In: 38th Annual International Colloquium on Automata, Languages and Programming, Volume 6755 of LNCS, pp. 379\u2013390 (2011)","DOI":"10.1007\/978-3-642-22006-7_32"},{"key":"850_CR7","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2, 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"4","key":"850_CR8","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1287\/opre.43.4.623","volume":"43","author":"O Berman","year":"1995","unstructured":"Berman, O., Bertsimas, D., Larson, R.C.: Locating discretionary service facilities, ii: maximizing market size, minimizing inconvenience. Oper. Res. 43(4), 623\u2013632 (1995)","journal-title":"Oper. Res."},{"issue":"4","key":"850_CR9","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1287\/trsc.26.3.201","volume":"26","author":"O Berman","year":"1992","unstructured":"Berman, O., Larson, R.C., Fouska, N.: Optimal location of discretionary service facilities. Transp. Sci. 26(4), 201\u2013611 (1992)","journal-title":"Transp. Sci."},{"key":"850_CR10","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973730.80"},{"issue":"3","key":"850_CR11","doi-asserted-by":"publisher","first-page":"30:1","DOI":"10.1145\/3309764","volume":"15","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Online submodular maximization with preemption. ACM Trans. Algorithms 15(3), 30:1\u201330:31 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"850_CR12","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"850_CR13","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: matchings, matroids, and more. In: 17th International Conference on Integer Programming and Combinatorial Optimization, Volume 8494 of LNCS, pp. 210\u2013221 (2014)","DOI":"10.1007\/978-3-319-07557-0_18"},{"issue":"3","key":"850_CR14","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)","journal-title":"Math. Oper. Res."},{"key":"850_CR15","doi-asserted-by":"crossref","unstructured":"Cygan, M., Je\u017c, L., Sgall, J.: Online knapsack revisited. Theor. Comput. Syst. 58(1), 153\u2013190 (2016)","DOI":"10.1007\/s00224-014-9566-4"},{"issue":"1\u20133","key":"850_CR16","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2004.08.015","volume":"332","author":"M Demange","year":"2005","unstructured":"Demange, M., Paschos, V.T.: On-line vertex-covering. Theor. Comput. Sci. 332(1\u20133), 83\u2013108 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"850_CR17","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129\u20131146 (2005)","journal-title":"SIAM J. Comput."},{"key":"850_CR18","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: The importance of being biased. In: 34th Annual ACM Symposium on the Theory of Computing, pp. 33\u201342 (2002)","DOI":"10.1145\/509907.509915"},{"issue":"4","key":"850_CR19","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)","journal-title":"J. ACM"},{"key":"850_CR20","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: Analysis of approximation algorithms for maximizing submodular set function II. Math. Program. Study 8, 73\u201387 (1978)","journal-title":"Math. Program. Study"},{"key":"850_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979)"},{"key":"850_CR22","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.tcs.2014.10.017","volume":"562","author":"X Han","year":"2015","unstructured":"Han, X., Kawase, Y., Makino, K.: Randomized algorithms for online knapsack problems. Theoret. Comput. Sci. 562, 395\u2013405 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"850_CR23","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"volume-title":"Approximation Algorithms for NP-Hard Problem","year":"1997","key":"850_CR24","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problem. PWS Publishing Company, New York (1997)"},{"issue":"6","key":"850_CR25","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5","volume":"45","author":"DS Hochbaum","year":"1998","unstructured":"Hochbaum, D.S., Pathria, A.: Analysis of the greedy approach in problems of maximum $$k$$-coverage. Nav. Res. Logist. 45(6), 615\u2013627 (1998)","journal-title":"Nav. Res. Logist."},{"issue":"4","key":"850_CR26","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"850_CR27","doi-asserted-by":"crossref","unstructured":"Iwama, K., Taketomi, S.: Removable online knapsack problems. In: 29th Annual International Colloquium on Automata, Languages and Programming, Volume 2380 of LNCS, pp. 293\u2013305 (2002)","DOI":"10.1007\/3-540-45465-9_26"},{"key":"850_CR28","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, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"850_CR29","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. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"850_CR30","doi-asserted-by":"crossref","unstructured":"Komm, D., Kr\u00e1lovic, R., M\u00f6mke, T.: On the advice complexity of the set cover problem. In: 7th International Computer Science Symposium in Russia, pp. 241\u2013252 (2012)","DOI":"10.1007\/978-3-642-30642-6_23"},{"key":"850_CR31","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 integeral and fractional solutions. Discret. Math. 13, 383\u2013390 (1975)","journal-title":"Discret. Math."},{"key":"850_CR32","first-page":"73","volume":"68","author":"A Marchetti-Spaccamela","year":"1995","unstructured":"Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68, 73\u2013104 (1995)","journal-title":"Math. Program."},{"issue":"2","key":"850_CR33","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1137\/0604028","volume":"4","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N., Zemel, E., Hakimi, S.L.: The maximum coverage location problem. SIAM J. Algebr. Discrete Methods 4(2), 253\u2013261 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"850_CR34","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Hoboken (1988)"},{"issue":"1","key":"850_CR35","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(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"850_CR36","unstructured":"Rawitz, D., Ros\u00e9n, A.: Online budgeted maximum coverage. In: 24th Annual European Symposium on Algorithms, Volume\u00a057 of LIPIcs, pp. 73:1\u201373:17 (2016)"},{"key":"850_CR37","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: 29th Annual ACM Symposium on the Theory of Computing, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"850_CR38","doi-asserted-by":"crossref","unstructured":"Saha, B., Getoor, L.: On maximum coverage in the streaming model & application to multi-topic blog-watch. In: SIAM International Conference on Data Mining, pp. 697\u2013708 (2009)","DOI":"10.1137\/1.9781611972795.60"},{"issue":"1","key":"850_CR39","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/321864.321873","volume":"22","author":"S Sahni","year":"1975","unstructured":"Sahni, S.: Approximate algorithms for the 0\/1 knapsack problem. J. ACM 22(1), 115\u2013124 (1975)","journal-title":"J. ACM"},{"issue":"1","key":"850_CR40","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. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"850_CR41","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"850_CR42","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Chakrabarty, D., Lukose, R.M.: Budget constrained bidding in keyword auctions and online knapsack problems. In: 4th international Workshop on Internet and Network Economics, Volume 5385 of LNCS, pp. 566\u2013576 (2008)","DOI":"10.1007\/978-3-540-92185-1_63"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00850-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00850-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00850-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:07:22Z","timestamp":1628161642000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00850-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,12]]},"references-count":42,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["850"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00850-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,7,12]]},"assertion":[{"value":"24 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}