{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:34:45Z","timestamp":1760056485983,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031931116"},{"type":"electronic","value":"9783031931123"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-93112-3_18","type":"book-chapter","created":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T04:56:03Z","timestamp":1749531363000},"page":"242-255","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Separating Coverage and\u00a0Submodular: Maximization Subject to\u00a0a\u00a0Cardinality Constraint"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1739-0872","authenticated-orcid":false,"given":"Yuval","family":"Filmus","sequence":"first","affiliation":[]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8241-5503","authenticated-orcid":false,"given":"Alexander V.","family":"Smal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,4]]},"reference":[{"issue":"3","key":"18_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.I.: 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."},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Ageev, A.A., Sviridenko, M.I.: Approximation algorithms for maximum coverage and max cut with given sizes of parts. In: Integer programming and combinatorial optimization (Graz, 1999), LNCS, vol.\u00a01610, pp. 17\u201330. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48777-8_2"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Austrin, P.: Balanced Max 2-Sat might not be the hardest. In: STOC\u201907\u2014Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 189\u2013197. ACM, New York (2007)","DOI":"10.1145\/1250790.1250818"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Austrin, P., Benabbas, S., Georgiou, K.: Better balance by being biased: a 0.8776-approximation for max bisection. ACM Trans. Algorithms 13(1) (2016)","DOI":"10.1145\/2907052"},{"key":"18_CR5","unstructured":"Austrin, P., Stankovi\u0107, A.: Global cardinality constraints make approximating some Max-2-CSPs harder. In: Approximation, randomization, and combinatorial optimization. Algorithms and techniques, LIPIcs. Leibniz Int. Proc. Inform., vol.\u00a0145, pp. Art. No. 24, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1497\u20131514. SODA \u201914, Society for Industrial and Applied Mathematics, USA (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Brakensiek, J., Huang, N., Zwick, U.: Tight approximability of MAX 2-SAT and relatives, under UGC. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1328\u20131344. SIAM, Philadelphia, PA (2024)","DOI":"10.1137\/1.9781611977912.53"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3) (2018)","DOI":"10.1145\/3184990"},{"issue":"3","key":"18_CR9","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1287\/moor.2018.0955","volume":"44","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder, N., Feldman, M.: Constrained submodular maximization via a nonsymmetric technique. Math. Oper. Res. 44(3), 988\u20131005 (2019)","journal-title":"Math. Oper. Res."},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Constrained submodular maximization via new bounds for dr-submodular functions. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, 24\u201328 June 2024, pp. 1820\u20131831. ACM (2024)","DOI":"10.1145\/3618260.3649630"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science\u2014FOCS 2024, pp. 700\u2013712. IEEE Computer Soc., Los Alamitos, CA ([2024] 2024)","DOI":"10.1109\/FOCS61266.2024.00050"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Extending the extension: Deterministic algorithm for non-monotone submodular maximization. In: 2025 IEEE 66th Annual Symposium on Foundations of Computer Science\u2014FOCS 2025. IEEE Computer Soc., Los Alamitos, CA ([2025] 2025)","DOI":"10.1145\/3717823.3718120"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1433\u20131452. ACM, New York (2014)","DOI":"10.1137\/1.9781611973730.80"},{"issue":"2","key":"18_CR14","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/moor.2016.0809","volume":"42","author":"N Buchbinder","year":"2017","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Comparing apples and oranges: query trade-off in submodular maximization. Math. Oper. Res. 42(2), 308\u2013329 (2017)","journal-title":"Math. Oper. Res."},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Online submodular maximization with preemption. ACM Trans. Algorithms 15(3) (2019)","DOI":"10.1145\/3309764"},{"key":"18_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 182\u2013196. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72792-7_15"},{"issue":"6","key":"18_CR17","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, 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)","journal-title":"SIAM J. Comput."},{"key":"18_CR18","doi-asserted-by":"publisher","unstructured":"Chan, T.H.H., Huang, Z., Jiang, S.H.C., Kang, N., Tang, Z.G.: Online submodular maximization with free disposal. ACM Trans. Algorithms 14(4), Art. 56, 29 (2018). https:\/\/doi.org\/10.1145\/3242770","DOI":"10.1145\/3242770"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science\u2014FOCS 2010, pp. 575\u2013584. IEEE Computer Soc., Los Alamitos, CA (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"3","key":"18_CR20","first-page":"1","volume":"19","author":"A Das","year":"2018","unstructured":"Das, A., Kempe, D.: Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection. J. Mach. Learn. Res. 19(3), 1\u201334 (2018)","journal-title":"J. Mach. Learn. Res."},{"key":"18_CR21","unstructured":"Dobzinski, S., Vondr\u00e1k, J.: The computational complexity of truthfulness in combinatorial auctions. ArXiv abs\/1202.2789 (2012). https:\/\/api.semanticscholar.org\/CorpusID:149760"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Roughgarden, T., Yan, Q.: From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. In: Proceedings of the forty-third Annual ACM Symposium on Theory of Computing (2011). https:\/\/api.semanticscholar.org\/CorpusID:9192953","DOI":"10.1145\/1993636.1993657"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Vondr\u00e1k, J.: Limitations of randomized mechanisms for combinatorial auctions. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 502\u2013511 (2011). https:\/\/api.semanticscholar.org\/CorpusID:7549214","DOI":"10.1109\/FOCS.2011.64"},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Ene, A., Nguyen, H.L.: Constrained submodular maximization: Beyond 1\/e. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9\u201311 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 248\u2013257. IEEE Computer Society (2016)","DOI":"10.1109\/FOCS.2016.34"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of $$\\ln {n}$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","DOI":"10.1145\/285055.285059"},{"issue":"4","key":"18_CR26","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"18_CR27","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 570\u2013579 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"key":"18_CR28","unstructured":"John: Is the maximum coverage problem remains as hard when taking most sets? Theoretical Computer Science Stack Exchange. https:\/\/cstheory.stackexchange.com\/q\/54170. Accessed 11 Apr 2024"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Influential nodes in a diffusion model for social networks. In: Proceedings of the 32nd International Conference on Automata, Languages and Programming, pp. 1127\u20131138. ICALP\u201905, Springer-Verlag, Berlin, Heidelberg (2005)","DOI":"10.1007\/11523468_91"},{"issue":"4","key":"18_CR30","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)","journal-title":"Theory Comput."},{"issue":"1","key":"18_CR31","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)","journal-title":"Inf. Process. Lett."},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"Lewin, M., Livnat, D., Zwick, U.: Improved rounding techniques for the max 2-sat and max di-cut problems. In: Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 67\u201382. Springer-Verlag (2002)","DOI":"10.1007\/3-540-47867-1_6"},{"key":"18_CR33","unstructured":"Li, W., Feldman, M., Kazemi, E., Karbasi, A.: Submodular maximization in clean linear time. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) Advances in Neural Information Processing Systems, vol.\u00a035, pp. 17473\u201317487. Curran Associates, Inc. (2022). https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/6faf3b8ed0df532c14d0fc009e451b6d-Paper-Conference.pdf"},{"key":"18_CR34","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondr\u00e1k, J., Krause, A.: Lazier than lazy greedy. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 1812\u20131818. AAAI\u201915, AAAI Press (2015)","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"18_CR35","unstructured":"Mitrovic, M., Kazemi, E., Zadimoghaddam, M., Karbasi, A.: Data summarization at scale: a two-stage submodular approach. In: International Conference on Machine Learning (2018)"},{"issue":"3","key":"18_CR36","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)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"18_CR37","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":"18_CR38","unstructured":"Norouzi-Fard, A., Tarnawski, J., Mitrovic, S., Zandieh, A., Mousavifar, A., Svensson, O.: Beyond 1\/2-approximation for submodular maximization on massive data streams. In: Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol.\u00a080, pp. 3829\u20133838. PMLR, 10\u201315 July 2018"},{"key":"18_CR39","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Tan, N.: Approximating csps with global cardinality constraints using sdp hierarchies. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 373\u2013387. SODA \u201912 (2012)","DOI":"10.1137\/1.9781611973099.33"},{"issue":"1","key":"18_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."},{"issue":"1","key":"18_CR41","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1137\/110832318","volume":"42","author":"J Vondr\u00e1k","year":"2013","unstructured":"Vondr\u00e1k, J.: Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1), 265\u2013304 (2013)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-93112-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T10:53:40Z","timestamp":1760007220000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-93112-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031931116","9783031931123"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-93112-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"4 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Baltimore, MD","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco25.cs.jhu.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}