{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T07:43:31Z","timestamp":1743147811274,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030752415"},{"type":"electronic","value":"9783030752422"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75242-2_12","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"173-186","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Multi-budget Maximum Weighted Coverage Problem"],"prefix":"10.1007","author":[{"given":"Francesco","family":"Cellinese","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianlorenzo","family":"D\u2019Angelo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianpiero","family":"Monaco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yllka","family":"Velaj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. In: Proceedings of FOCS, pp. 649\u2013658 (2012). https:\/\/doi.org\/10.1109\/FOCS.2012.73","DOI":"10.1109\/FOCS.2012.73"},{"issue":"6","key":"12_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":"12_CR3","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s10878-011-9417-z","volume":"25","author":"I Caragiannis","year":"2013","unstructured":"Caragiannis, I., Monaco, G.: A 6\/5-approximation algorithm for the maximum 3-cover problem. J. Comb. Optim. 25(1), 60\u201377 (2013). https:\/\/doi.org\/10.1007\/s10878-011-9417-z","journal-title":"J. Comb. Optim."},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Cellinese, F., D\u2019Angelo, G., Monaco, G., Velaj, Y.: Generalized budgeted submodular set function maximization. In: Proceedings of MFCS. LIPIcs, vol. 117, pp. 31:1\u201331:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.31","DOI":"10.4230\/LIPIcs.MFCS.2018.31"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. In: Proceedings of FOCS, pp. 687\u2013696 (2008). https:\/\/doi.org\/10.1137\/080735503","DOI":"10.1137\/080735503"},{"key":"12_CR6","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX\/RANDOM-2004. LNCS, vol. 3122, pp. 72\u201383. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27821-4_7","DOI":"10.1007\/978-3-540-27821-4_7"},{"issue":"6","key":"12_CR7","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"12_CR8","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). https:\/\/doi.org\/10.1016\/j.ipl.2008.03.017","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"12_CR9","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1007\/s10878-016-0102-0","volume":"34","author":"B Farbstein","year":"2017","unstructured":"Farbstein, B., Levin, A.: Maximum coverage problem with group budget constraints. J. Comb. Optim. 34(3), 725\u2013735 (2017). https:\/\/doi.org\/10.1007\/s10878-016-0102-0","journal-title":"J. Comb. Optim."},{"key":"12_CR10","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\/237814.237977","DOI":"10.1145\/237814.237977"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. In: Proceedings of FOCS, pp. 461\u2013471 (2007). https:\/\/doi.org\/10.1137\/090779346","DOI":"10.1137\/090779346"},{"issue":"2","key":"12_CR12","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":"12_CR13","doi-asserted-by":"publisher","unstructured":"Gairing, M.: Covering games: approximation through non-cooperation. In: Proceedings of WINE, pp. 184\u2013195 (2009). https:\/\/doi.org\/10.1007\/978-3-642-10841-9_18","DOI":"10.1007\/978-3-642-10841-9_18"},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Goel, G., Karande, C., Tripathi, P., Wang, L.: Approximability of combinatorial problems with multi-agent submodular cost functions. In: Proceedings of FOCS, pp. 755\u2013764 (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.81","DOI":"10.1109\/FOCS.2009.81"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Goel, G., Tripathi, P., Wang, L.: Combinatorial problems with discounted price functions in multi-agent systems. In: Proceedings of the FSTTCS, pp. 436\u2013446 (2010). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2010.436","DOI":"10.4230\/LIPIcs.FSTTCS.2010.436"},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Hochbaum, D.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston (1997). https:\/\/doi.org\/10.1145\/261342.571216","DOI":"10.1145\/261342.571216"},{"key":"12_CR17","doi-asserted-by":"publisher","unstructured":"Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: Proceedings of FOCS, pp. 671\u2013680 (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.31","DOI":"10.1109\/FOCS.2009.31"},{"key":"12_CR18","doi-asserted-by":"publisher","unstructured":"Iyer, R.K., Bilmes, J.A.: Submodular optimization with submodular cover and submodular knapsack constraints. In: Proceedings of NIPS, pp. 2436\u20132444 (2013). https:\/\/doi.org\/10.1145\/1374376.1374389","DOI":"10.1145\/1374376.1374389"},{"issue":"1","key":"12_CR19","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.S.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999). https:\/\/doi.org\/10.1016\/S0020-0190(99)00031-9","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"12_CR20","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)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"12_CR21","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/978-3-642-03685-9_19","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.1007\/978-3-642-03685-9_19","journal-title":"Math. Oper. Res."},{"issue":"1","key":"12_CR22","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1287\/opre.1120.1137","volume":"61","author":"JR Marden","year":"2013","unstructured":"Marden, J.R., Wierman, A.: Distributed welfare games. Oper. Res. 61(1), 155\u2013168 (2013). https:\/\/doi.org\/10.1287\/opre.1120.1137","journal-title":"Oper. Res."},{"issue":"1","key":"12_CR23","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). https:\/\/doi.org\/10.1007\/BF01588971","journal-title":"Math. Program."},{"key":"12_CR24","doi-asserted-by":"publisher","unstructured":"Santiago, R., Shepherd, F.B.: Multi-agent submodular optimization. In: Proceedings of APPROX\/RANDOM. LIPIcs, vol. 116, pp. 23:1\u201323:20 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.23","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.23"},{"key":"12_CR25","unstructured":"Santiago, R., Shepherd, F.B.: Multivariate submodular optimization. In: Proceedings of ICML, vol. 97, pp. 5599\u20135609. PMLR (2019)"},{"issue":"1","key":"12_CR26","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). https:\/\/doi.org\/10.1016\/S0167-6377(03)00062-2","journal-title":"Oper. Res. Lett."},{"key":"12_CR27","doi-asserted-by":"publisher","unstructured":"Vondrak, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of STOC, pp. 67\u201374. ACM (2008). https:\/\/doi.org\/10.1145\/1374376.1374389","DOI":"10.1145\/1374376.1374389"},{"key":"12_CR28","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: Proceedings of STACS, pp. 42\u201353 (2012). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.42","DOI":"10.4230\/LIPIcs.STACS.2012.42"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75242-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:26:25Z","timestamp":1620141985000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic the conference was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}