{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T07:08:24Z","timestamp":1784358504468,"version":"3.55.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T00:00:00Z","timestamp":1532304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T00:00:00Z","timestamp":1532304000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0953754"],"award-info":[{"award-number":["CCF-0953754"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1251110"],"award-info":[{"award-number":["IIS-1251110"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00224-018-9878-x","type":"journal-article","created":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T05:01:27Z","timestamp":1532322087000},"page":"1595-1619","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Better Streaming Algorithms for the Maximum Coverage Problem"],"prefix":"10.1007","volume":"63","author":[{"given":"Andrew","family":"McGregor","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8873-0208","authenticated-orcid":false,"given":"Hoa T.","family":"Vu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,7,23]]},"reference":[{"key":"9878_CR1","doi-asserted-by":"crossref","unstructured":"Ageev, A.A., Sviridenko, M.: Approximation algorithms for maximum coverage and max cut with given sizes of parts. In: IPCO, volume 1610 of Lecture Notes in Computer Science, pp. 17\u201330. Springer (1999)","DOI":"10.1007\/3-540-48777-8_2"},{"issue":"3","key":"9878_CR2","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."},{"key":"9878_CR3","unstructured":"Ahn, K.J, Cormode, G., Guha, S., McGregor, A., Wirth, A.: Correlation clustering in data streams. In: ICML, volume 37 of JMLR Workshop and Conference Proceedings, pp. 2237\u20132246, JMLR.org (2015)"},{"key":"9878_CR4","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: SODA, pp. 459\u2013467. SIAM (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"9878_CR5","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: PODS, pp. 5\u201314. ACM (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"9878_CR6","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Spectral sparsification in dynamic graph streams. In: APPROX-RANDOM, volume 8096 of Lecture Notes in Computer Science, pp. 1\u201310. Springer (2013)","DOI":"10.1007\/978-3-642-40328-6_1"},{"issue":"3","key":"9878_CR7","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/2699671","volume":"33","author":"A Anagnostopoulos","year":"2015","unstructured":"Anagnostopoulos, A., Becchetti, L., Bordino, I., Leonardi, S., Mele, I., Sankowski, P.: Stochastic query covering for fast approximate document retrieval. ACM Trans. Inf. Syst. 33(3), 11:1\u201311:35 (2015)","journal-title":"ACM Trans. Inf. Syst."},{"key":"9878_CR8","doi-asserted-by":"crossref","unstructured":"Assadi, S.: Tight space-approximation tradeoff for the multi-pass streaming set cover problem. In: PODS, pp. 321\u2013335. ACM (2017)","DOI":"10.1145\/3034786.3056116"},{"key":"9878_CR9","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y.: Tight bounds for single-pass streaming complexity of the set cover problem. In: STOC, pp. 698\u2013711. ACM (2016)","DOI":"10.1145\/2897518.2897576"},{"key":"9878_CR10","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Maximum matchings in dynamic graph streams and the simultaneous communication model. In: SODA, pp. 1345\u20131364. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch93"},{"issue":"13-14","key":"9878_CR11","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.Th.: Online maximum k-coverage. Discret. Appl. Math. 160(13-14), 1901\u20131913 (2012)","journal-title":"Discret. Appl. Math."},{"key":"9878_CR12","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. In: KDD, pp. 671\u2013680. ACM (2014)","DOI":"10.1145\/2623330.2623637"},{"key":"9878_CR13","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: SODA, pp. 1497\u20131514. SIAM (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"9878_CR14","doi-asserted-by":"crossref","unstructured":"Bateni, M.H., Esfandiari, H., Mirrokni, V.S.: Almost optimal streaming algorithms for coverage problems CoRR, arXiv:\n                    1610.08096\n                    \n                   (2016)","DOI":"10.1145\/3087556.3087585"},{"key":"9878_CR15","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D., Tsourakakis, C.E.: Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: STOC, pp. 173\u2013182. ACM (2015)","DOI":"10.1145\/2746539.2746592"},{"key":"9878_CR16","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Escoffier, B., Paschos, V.Th., Stamoulis, G.: A 0.821-ratio purely combinatorial algorithm for maximum k-vertex cover in bipartite graphs. In: LATIN, volume 9644 of Lecture Notes in Computer Science, pp. 235\u2013248. Springer (2016)","DOI":"10.1007\/978-3-662-49529-2_18"},{"key":"9878_CR17","doi-asserted-by":"crossref","unstructured":"Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: On partial vertex cover and budgeted maximum coverage problems in bipartite graphs. In: IFIP TCS, volume 8705 of Lecture Notes in Computer Science, pp. 13\u201326. Springer (2014)","DOI":"10.1007\/978-3-662-44602-7_2"},{"key":"9878_CR18","first-page":"62","volume":"18","author":"A Chakrabarti","year":"2011","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A.: Robust lower bounds for communication and stream computation. Electronic Colloquium on Computational Complexity (ECCC) 18, 62 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"9878_CR19","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: Matchings, matroids, and more. In: IPCO, volume 8494 of Lecture Notes in Computer Science, pp. 210\u2013221. Springer (2014)","DOI":"10.1007\/978-3-319-07557-0_18"},{"key":"9878_CR20","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. IEEE Computer Society (2003)"},{"key":"9878_CR21","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Wirth, A.: Incidence geometries and the pass complexity of semi-streaming set cover. In: SODA, pp. 1365\u20131373. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch94"},{"key":"9878_CR22","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Gupta, S., Quanrud, K.: Streaming algorithms for submodular function maximization. In: ICALP (1), volume 9134 of Lecture Notes in Computer Science, pp. 318\u2013330. Springer (2015)","DOI":"10.1007\/978-3-662-47672-7_26"},{"key":"9878_CR23","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: APPROX-RANDOM, volume 3122 of Lecture Notes in Computer Science, pp. 72\u201383. Springer (2004)","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"9878_CR24","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M.T., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In: SODA, pp. 1326\u20131344. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch92"},{"issue":"3","key":"9878_CR25","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/TKDE.2003.1198388","volume":"15","author":"G Cormode","year":"2003","unstructured":"Cormode, G., Datar, M., Indyk, P., Muthukrishnan, S.: Comparing data streams using hamming (how to zero in). IEEE Trans. Knowl. Data Eng. 15(3), 529\u2013540 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"9878_CR26","doi-asserted-by":"crossref","unstructured":"Cormode, G., Karloff, H.J., Wirth, A.: Set cover algorithms for very large datasets. In: CIKM, pp. 479\u2013488. ACM (2010)","DOI":"10.1145\/1871437.1871501"},{"key":"9878_CR27","doi-asserted-by":"crossref","unstructured":"Emek, Y., Ros\u00e9n, A.: Semi-streaming set cover - (extended abstract). In: ICALP (1), volume 8572 of Lecture Notes in Computer Science, pp. 453\u2013464. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_38"},{"issue":"4","key":"9878_CR28","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":"9878_CR29","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hyperedge connectivity in dynamic graph streams. In: PODS, pp. 241\u2013247. ACM (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"9878_CR30","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Indyk, P., Mahabadi, S., Vakilian, A.: Towards tight bounds for the streaming set cover problem. In: PODS, pp. 371\u2013383. ACM (2016)","DOI":"10.1145\/2902251.2902287"},{"key":"9878_CR31","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. IEEE Computer Society (2014)","DOI":"10.1109\/FOCS.2014.66"},{"key":"9878_CR32","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Woodruff, D.P.: Spanners and sparsifiers in dynamic streams. In: PODC, pp. 272\u2013281. ACM (2014)","DOI":"10.1145\/2611462.2611497"},{"key":"9878_CR33","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.M., Tardos, \u00c9.: Maximizing the spread of influence through a social network. Theory of Computing 11, 105\u2013147 (2015)","journal-title":"Theory of Computing"},{"issue":"1","key":"9878_CR34","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":"9878_CR35","doi-asserted-by":"crossref","unstructured":"Kogan, D., Krauthgamer, R.: Sketching cuts in graphs and hypergraphs. In 6th Innovations in Theoretical Computer Science (2015)","DOI":"10.1145\/2688073.2688093"},{"key":"9878_CR36","doi-asserted-by":"crossref","unstructured":"Konrad, C.: Maximum matching in turnstile streams. In: ESA, volume 9294 of Lecture Notes in Computer Science, pp. 840\u2013852. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_70"},{"key":"9878_CR37","unstructured":"Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In: AAAI, pp. 1650\u20131654. AAAI Press (2007)"},{"issue":"3","key":"9878_CR38","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2809814","volume":"2","author":"R Kumar","year":"2015","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. TOPC 2(3), 14 (2015)","journal-title":"TOPC"},{"issue":"1","key":"9878_CR39","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Record 43(1), 9\u201320 (2014)","journal-title":"SIGMOD Record"},{"key":"9878_CR40","doi-asserted-by":"crossref","unstructured":"McGregor, A., Tench, D., Vorotnikova, S., Vu, H.T.: Densest subgraph in dynamic graph streams. In: MFCS (2), volume 9235 of Lecture Notes in Computer Science, pp. 472\u2013482. Springer (2015)","DOI":"10.1007\/978-3-662-48054-0_39"},{"key":"9878_CR41","doi-asserted-by":"crossref","unstructured":"McGregor, A., Vorotnikova, S., Vu, H.T.: Better algorithms for counting triangles in data streams. In: PODS, pp. 401\u2013411. ACM (2016)","DOI":"10.1145\/2902251.2902283"},{"key":"9878_CR42","unstructured":"McGregor, A., Vu, H.T.: Better streaming algorithms for the maximum coverage problem. In: ICDT, volume 68 of LIPIcs, pp. 22:1\u201322:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"2","key":"9878_CR43","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"key":"9878_CR44","doi-asserted-by":"crossref","unstructured":"Radhakrishnan, J., Shannigrahi, S.: Streaming algorithms for 2-coloring uniform hypergraphs. In: Algorithms and Data Structures - 12th International Symposium, WADS 2011, New york. Proceedings, pp. 667\u2013678 (2011)","DOI":"10.1007\/978-3-642-22300-6_57"},{"key":"9878_CR45","doi-asserted-by":"crossref","unstructured":"Saha, B., Getoor, L.: On maximum coverage in the streaming model & application to multi-topic blog-watch. In: SDM, pp. 697\u2013708. SIAM (2009)","DOI":"10.1137\/1.9781611972795.60"},{"issue":"2","key":"9878_CR46","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"JP Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-hoeffding bounds for applications with limited independence. SIAM J. Discrete Math. 8(2), 223\u2013250 (1995)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"9878_CR47","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Teng, S.H.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981\u20131025 (2011)","journal-title":"SIAM J. Comput."},{"key":"9878_CR48","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Distributions on level-sets with applications to approximation algorithms. In: FOCS, pp. 588\u2013597. IEEE Computer Society (2001)","DOI":"10.1109\/SFCS.2001.959935"},{"key":"9878_CR49","unstructured":"Sun, H.: Counting hypergraphs in data streams. CoRR, arXiv:\n                    1304.7456\n                    \n                   (2013)"},{"key":"9878_CR50","doi-asserted-by":"crossref","unstructured":"Yu, H., Yuan, D.: Set coverage problems in a one-pass data stream. In: SDM, pp. 758\u2013766. SIAM (2013)","DOI":"10.1137\/1.9781611972832.84"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9878-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9878-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9878-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T05:39:07Z","timestamp":1589693947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9878-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,23]]},"references-count":50,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["9878"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9878-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,23]]},"assertion":[{"value":"23 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}