{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:50Z","timestamp":1787340410429,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1116961"],"award-info":[{"award-number":["CCF-1116961"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1552909"],"award-info":[{"award-number":["CCF-1552909"]}],"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-1447470"],"award-info":[{"award-number":["IIS-1447470"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\\alpha$-approximate set cover (for any $\\alpha=o(\\sqrt{n}\/\\log n)$) using a single-pass streaming algorithm, we show that $\\Theta(mn\/\\alpha)$ space is both sufficient and necessary (up to an $O(\\log n)$ factor); here $m$ denotes the number of sets and $n$ denotes the size of the universe. This provides a strong negative answer to the open question posed by Har-Peled et al. [ Towards tight bounds for the streaming set cover problem, in Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS '16), pp. 371--383] regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sublinear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets) and establish that an additional factor of $\\alpha$ savings in the space is achievable in this case and is the best possible. In other words, we show that $\\Theta(mn\/\\alpha^2)$ space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of $\\alpha$. Our algorithm, in fact, works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances, where the sets are presented in a random order.<\/jats:p>","DOI":"10.1137\/16m1095482","type":"journal-article","created":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T13:09:52Z","timestamp":1571922592000},"page":"STOC16-341-STOC16-376","source":"Crossref","is-referenced-by-count":9,"title":["Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem"],"prefix":"10.1137","volume":"50","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,10,24]]},"reference":[{"key":"atypb1","first-page":"20","author":"Alon N.","year":"1996","journal-title":"Philadelphia"},{"key":"atypb2","first-page":"321","author":"Assadi S.","year":"2017","journal-title":"Chicago"},{"key":"atypb3","first-page":"2412","author":"Assadi S.","year":"2018","journal-title":"LA"},{"key":"atypb4","first-page":"698","author":"Assadi S.","year":"2016","journal-title":"MA"},{"key":"atypb5","first-page":"209","author":"Bar-Yossef Z.","year":"2002","journal-title":"Vancouver, BC, Canada"},{"key":"atypb6","first-page":"93","author":"Bar-Yossef Z.","year":"2002","journal-title":"Montr\u00e9al, QC, Canada"},{"key":"atypb7","first-page":"67","author":"Barak B.","year":"2010","journal-title":"MA"},{"key":"atypb8","first-page":"13","author":"Bateni M.","year":"2017","journal-title":"Washington, DC"},{"key":"atypb9","first-page":"641","author":"Chakrabarti A.","year":"2008","journal-title":"Victoria, BC, Canada"},{"key":"atypb10","first-page":"270","author":"Chakrabarti A.","year":"2001","journal-title":"NV"},{"key":"atypb11","first-page":"1365","author":"Chakrabarti A.","year":"2016","journal-title":"VA"},{"key":"atypb12","first-page":"479","author":"Cormode G.","year":"2010","journal-title":"Canada"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"T. M. Cover and J. A. Thomas,\n                      Elements of Information Theory\n                      , 2nd ed., Wiley, 2006.","DOI":"10.1002\/047174882X"},{"key":"atypb14","first-page":"484","author":"Demaine E. D.","year":"2014","journal-title":"TX"},{"key":"atypb15","first-page":"624","author":"Dinur I.","year":"2014","journal-title":"NY"},{"key":"atypb16","first-page":"453","author":"Emek Y.","year":"2014","journal-title":"Denmark"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"S. Har-Peled, P. Indyk, S. Mahabadi, and A. Vakilian,\n                      Towards tight bounds for the streaming set cover problem\n                      , in Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2016), San Francisco, CA, 2016, pp. 371-383.","DOI":"10.1145\/2902251.2902287"},{"key":"atypb20","first-page":"617","author":"Impagliazzo R.","year":"2010","journal-title":"Spain"},{"key":"atypb21","unstructured":"P. Indyk, S. Mahabadi, R. Rubinfeld, J. Ullman, A. Vakilian, and A. Yodpinyanee,\n                      Fractional set cover in the streaming model\n                      , in Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2017) and the 21st International Workshop on Randomization and Computation (RANDOM 2017) Berkeley, CA, 2017, 12."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"T. S. Jayram and D. Woodruff,\n                      Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, CA, 2011, pp. 1-10,https:\/\/doi.org\/10.1137\/1.9781611973082.1.","DOI":"10.1137\/1.9781611973082.1"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"atypb24","first-page":"734","author":"Kapralov M.","year":"2014","journal-title":"OR"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan,\n                      Communication Complexity\n                      , Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"atypb28","first-page":"868","author":"Nisan N.","year":"2002","journal-title":"Spain"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"atypb30","unstructured":"M. Saglam,\n                      Tight Bounds for Data Stream Algorithms and Communication Problems\n                      , Ph.D. thesis, Simon Fraser University, 2011."},{"key":"atypb31","first-page":"697","author":"Saha B.","year":"2009","journal-title":"NV"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0887"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1095482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:52Z","timestamp":1787337232000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1095482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,24]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/16M1095482"],"URL":"https:\/\/doi.org\/10.1137\/16m1095482","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,24]]}}}