{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:17Z","timestamp":1779174857505,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE47-0011"],"award-info":[{"award-number":["ANR-18-CE47-0011"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s10107-021-01677-4","type":"journal-article","created":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T16:09:35Z","timestamp":1625155775000},"page":"443-476","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Tight approximation bounds for maximum multi-coverage"],"prefix":"10.1007","volume":"192","author":[{"given":"Siddharth","family":"Barman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8491-0359","authenticated-orcid":false,"given":"Omar","family":"Fawzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suprovat","family":"Ghoshal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emirhan","family":"G\u00fcrp\u0131nar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,1]]},"reference":[{"issue":"3","key":"1677_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":"1677_CR2","doi-asserted-by":"crossref","unstructured":"Barman, S., Fawzi, O.: Algorithmic aspects of optimal channel coding. IEEE Trans. Inform. Theory. (2018). arXiv:1508.04095","DOI":"10.1109\/TIT.2017.2696963"},{"key":"1677_CR3","unstructured":"Barman, S., Fawzi, O., Ferm\u00e9, P.: Tight approximation guarantees for concave coverage problems. (2020). arXiv preprint arXiv:2010.00970"},{"issue":"6","key":"1677_CR4","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1016\/j.dam.2004.11.009","volume":"155","author":"P Berman","year":"2007","unstructured":"Berman, P., DasGupta, B., Sontag, E.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discrete Appl. Math. 155(6), 733\u2013749 (2007). (Computational Molecular Biology Series, Issue V)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1677_CR5","doi-asserted-by":"publisher","first-page":"2626","DOI":"10.1137\/16M1082421","volume":"31","author":"A Bhangale","year":"2017","unstructured":"Bhangale, A., Gandhi, R., Hajiaghayi, M.T., Khandekar, R., Kortsarz, G.: Bi-covering: covering edges with two small subsets of vertices. SIAM J. Discrete Math. 31(4), 2626\u20132646 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"1677_CR6","doi-asserted-by":"crossref","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.) Proceedings of IPCO, pp. 182\u2013196. Springer, Berlin","DOI":"10.1007\/978-3-540-72792-7_15"},{"issue":"6","key":"1677_CR7","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":"1677_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: Proceedings of FOCS, pp. 575\u2013584. IEEE (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"3","key":"1677_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti, M., Cornu\u00e9jols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado\u2013Edmonds theorem. Discrete Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"1677_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.: Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Manage. Sci. 23(8), 789\u2013810 (1977)","journal-title":"Manage. Sci."},{"issue":"4","key":"1677_CR11","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G Dobson","year":"1982","unstructured":"Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res. 7(4), 515\u2013531 (1982)","journal-title":"Math. Oper. Res."},{"key":"1677_CR12","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of ACM-SIAM SODA, pp. 1064\u20131073. Society for Industrial and Applied Mathematics (2006)","DOI":"10.1145\/1109557.1109675"},{"key":"1677_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"1677_CR14","doi-asserted-by":"crossref","unstructured":"Dubhashi, D.P., Ranjan, D.: Balls and bins: a study in negative dependence. BRICS report series, vol. 3, issue 25 (1996)","DOI":"10.7146\/brics.v3i25.20006"},{"key":"1677_CR15","doi-asserted-by":"crossref","unstructured":"Dudycz, S., Manurangsi, P., Marcinkowski, J., Sornat, K.: Tight approximation for proportional approval voting. In: Proceedings of IJCAI\u201920, pp. 276\u2013282 (2020)","DOI":"10.24963\/ijcai.2020\/39"},{"issue":"4","key":"1677_CR16","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/2908735","volume":"63","author":"S Dughmi","year":"2016","unstructured":"Dughmi, S., Roughgarden, T., Yan, Q.: Optimal mechanisms for combinatorial auctions and combinatorial public projects via convex rounding. J. ACM 63(4), 30 (2016)","journal-title":"J. ACM"},{"key":"1677_CR17","unstructured":"Dughmi, S., Vondr\u00e1k, J.: Limitations of randomized mechanisms for combinatorial auctions. In: Proceedings of FOCS, pp. 502\u2013511. IEEE Computer Society, Washington"},{"issue":"4","key":"1677_CR18","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"},{"issue":"1","key":"1677_CR19","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/070680977","volume":"39","author":"U Feige","year":"2009","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39(1), 122\u2013142 (2009)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1677_CR20","doi-asserted-by":"publisher","first-page":"1558","DOI":"10.1137\/120865094","volume":"41","author":"V Feldman","year":"2012","unstructured":"Feldman, V., Guruswami, V., Raghavendra, P., Wu, Y.: Agnostic learning of monomials by halfspaces is hard. SIAM J. Comput. 41(6), 1558\u20131590 (2012)","journal-title":"SIAM J. Comput."},{"key":"1677_CR21","unstructured":"Feldman, V., Kothari, P.: Learning coverage functions and private release of marginals. In: Proceedings of COLT, pp. 679\u2013702 (2014)"},{"key":"1677_CR22","unstructured":"Hochbaum, D.S.: Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In: Approximation algorithms for np-hard problem, pp. 94\u2013143. PWS Pub. (1997)"},{"key":"1677_CR23","doi-asserted-by":"crossref","unstructured":"Joag-Dev, K., Proschan, F.: Negative association of random variables with applications. Ann. Stat. 286\u2013295 (1983)","DOI":"10.1214\/aos\/1176346079"},{"issue":"3","key":"1677_CR24","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(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"1677_CR25","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of ACM STOC, pp. 767\u2013775. ACM (2002)","DOI":"10.1145\/509907.510017"},{"key":"1677_CR26","unstructured":"Khot, S., Vishnoi, N.K.: On the unique games conjecture. In: Proceedings FOCS, vol.\u00a05, p.\u00a03 (2005)"},{"key":"1677_CR27","first-page":"19","volume":"3","author":"A Krause","year":"2012","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. Tractability Pract. Approaches Hard Probl. 3, 19 (2012)","journal-title":"Tractability Pract. Approaches Hard Probl."},{"key":"1677_CR28","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D.: The projection games conjecture and the NP-hardness of ln n-approximating set-cover. In: Proceedings of APPROX-RANDOM, pp. 276\u2013287. Springer (2012)","DOI":"10.1007\/978-3-642-32512-0_24"},{"issue":"1","key":"1677_CR29","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. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"5","key":"1677_CR30","doi-asserted-by":"publisher","first-page":"2307","DOI":"10.1109\/TIT.2010.2043769","volume":"56","author":"Y Polyanskiy","year":"2010","unstructured":"Polyanskiy, Y., Poor, H.V., Verd\u00fa, S.: Channel coding rate in the finite blocklength regime. IEEE Trans. Inform. Theory 56(5), 2307\u20132359 (2010)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"1677_CR31","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1137\/S0097539793260763","volume":"28","author":"S Rajagopalan","year":"1998","unstructured":"Rajagopalan, S., Vazirani, V.V.: Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput. 28(2), 525\u2013540 (1998)","journal-title":"SIAM J. Comput."},{"key":"1677_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-34675-5","volume-title":"Stochastic Orders","author":"M Shaked","year":"2007","unstructured":"Shaked, M., Shanthikumar, J.G.: Stochastic Orders. Springer, Berlin (2007)"},{"issue":"4","key":"1677_CR33","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"M Sviridenko","year":"2017","unstructured":"Sviridenko, M., Vondr\u00e1k, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197\u20131218 (2017)","journal-title":"Math. Oper. Res."},{"key":"1677_CR34","unstructured":"Vondr\u00e1k, J.: Submodularity in combinatorial optimization. PhD thesis, Charles University (2007)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01677-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01677-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01677-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:19:07Z","timestamp":1646846347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01677-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,1]]},"references-count":34,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1677"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01677-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,1]]},"assertion":[{"value":"24 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}