{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:24:09Z","timestamp":1743053049172,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030457709"},{"type":"electronic","value":"9783030457716"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-45771-6_6","type":"book-chapter","created":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T21:03:32Z","timestamp":1586811812000},"page":"66-77","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Tight Approximation Bounds for Maximum Multi-coverage"],"prefix":"10.1007","author":[{"given":"Siddharth","family":"Barman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[[2020,4,14]]},"reference":[{"issue":"3","key":"6_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":"6_CR2","unstructured":"Barman, S., Fawzi, O.: Algorithmic aspects of optimal channel coding. IEEE Trans. Inform. Theory (2018). \narXiv:1508.04095"},{"key":"6_CR3","unstructured":"Barman, S., Fawzi, O., Ghoshal, S., G\u00fcrp\u0131nar, E.: Tight approximation bounds for maximum multi-coverage (2019). \narXiv:1905.00640"},{"issue":"6","key":"6_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). \nhttps:\/\/doi.org\/10.1016\/j.dam.2004.11.009\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X06003659\n\n. Computational Molecular Biology Series, Issue V","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"6_CR5","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."},{"issue":"1","key":"6_CR6","first-page":"9","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms (TALG) 9(1), 9 (2012)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"6_CR7","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-Edmonds theorem. Discrete Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"6_CR8","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. Manag. Sci. 23(8), 789\u2013810 (1977). \nhttps:\/\/doi.org\/10.1287\/mnsc.23.8.789","journal-title":"Manag. Sci."},{"issue":"4","key":"6_CR9","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":"6_CR10","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 1064\u20131073. Society for Industrial and Applied Mathematics (2006)","DOI":"10.1145\/1109557.1109675"},{"issue":"4","key":"6_CR11","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 (JACM) 63(4), 30 (2016)","journal-title":"J. ACM (JACM)"},{"key":"6_CR12","doi-asserted-by":"publisher","unstructured":"Dughmi, S., Vondr\u00e1k, J.: Limitations of randomized mechanisms for combinatorial auctions. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp. 502\u2013511. IEEE Computer Society, Washington, DC (2011). \nhttps:\/\/doi.org\/10.1109\/FOCS.2011.64","DOI":"10.1109\/FOCS.2011.64"},{"issue":"4","key":"6_CR13","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":"6_CR14","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."},{"key":"6_CR15","unstructured":"Feldman, V., Kothari, P.: Learning coverage functions and private release of marginals. In: Conference on Learning Theory, pp. 679\u2013702 (2014)"},{"key":"6_CR16","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":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-10631-6_6","volume-title":"Algorithms and Computation","author":"Q-S Hua","year":"2009","unstructured":"Hua, Q.-S., Yu, D., Lau, F.C.M., Wang, Y.: Exact algorithms for set multicover and multiset multicover problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 34\u201344. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-10631-6_6"},{"issue":"3","key":"6_CR18","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":"6_CR19","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 767\u2013775. ACM (2002)","DOI":"10.1145\/509907.510017"},{"key":"6_CR20","unstructured":"Khot, S., Vishnoi, N.K.: On the unique games conjecture. In: FOCS, vol. 5, p. 3 (2005)"},{"key":"6_CR21","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In: Tractability: Practical Approaches to Hard Problems, vol. 3, p. 19 (2012)"},{"issue":"1","key":"6_CR22","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":"6_CR23","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. Inf. Theory 56(5), 2307\u20132359 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"6_CR24","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":"6_CR25","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, New York (2007). \nhttps:\/\/doi.org\/10.1007\/978-0-387-34675-5"},{"issue":"4","key":"6_CR26","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":"6_CR27","unstructured":"Vondr\u00e1k, J.: Submodularity in combinatorial optimization (2007)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45771-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T23:10:00Z","timestamp":1589929800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45771-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030457709","9783030457716"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45771-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"14 April 2020","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":"London","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.xixilogic.org\/events\/clar2020\/","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":"126","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":"33","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":"26% - 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":"26","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":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}