{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:12Z","timestamp":1763468232909},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662451731"},{"type":"electronic","value":"9783662451748"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-45174-8_33","type":"book-chapter","created":{"date-parts":[[2014,9,29]],"date-time":"2014-09-29T15:28:20Z","timestamp":1412004500000},"page":"484-498","source":"Crossref","is-referenced-by-count":8,"title":["On Streaming and Communication Complexity of the Set Cover Problem"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"Piotr","family":"Indyk","sequence":"additional","affiliation":[]},{"given":"Sepideh","family":"Mahabadi","sequence":"additional","affiliation":[]},{"given":"Ali","family":"Vakilian","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"33_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms\u00a02(2), 153\u2013177 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"33_CR2","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Kumar, R., Tomkins, A.: Max-cover in map-reduce. In: Proc. of WWW, pp. 231\u2013240. ACM (2010)","DOI":"10.1145\/1772690.1772715"},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"Cormode, G., Karloff, H., Wirth, A.: Set cover algorithms for very large datasets. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management, pp. 479\u2013488. ACM (2010)","DOI":"10.1145\/1871437.1871501"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"Dolev, D., Feder, T.: Multiparty communication complexity. In: Proc. of IEEE FOCS, pp. 428\u2013433. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63514"},{"issue":"1","key":"33_CR5","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1006\/jcss.1997.1547","volume":"56","author":"P. \u010euri\u0161","year":"1998","unstructured":"\u010euri\u0161, P., Rolim, J.D.P.: Lower bounds on the multiparty communication complexity. Journal of Computer and System Sciences\u00a056(1), 90\u201395 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Emek, Y., Ros\u00e9n, A.: Semi-streaming set cover. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. Part I. LNCS, vol.\u00a08572, pp. 453\u2013464. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-43948-7_38"},{"issue":"1","key":"33_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0377-2217(96)00161-0","volume":"101","author":"T. Grossman","year":"1997","unstructured":"Grossman, T., Wool, A.: Computational experience with approximation algorithms for the set covering problem. European Journal of Operational Research\u00a0101(1), 81\u201392 (1997)","journal-title":"European Journal of Operational Research"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1007\/978-3-540-70575-8_62","volume-title":"Automata, Languages and Programming","author":"S. Guha","year":"2008","unstructured":"Guha, S., McGregor, A.: Tight lower bounds for multi-pass stream computation via pass elimination. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 760\u2013772. Springer, Heidelberg (2008)"},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. In: Proc. of SPAA, pp. 1\u201310. ACM (2013)","DOI":"10.1145\/2486159.2486168"},{"issue":"5","key":"33_CR10","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM\u00a041(5), 960\u2013981 (1994)","journal-title":"Journal of the ACM"},{"key":"33_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/3-540-45465-9_74","volume-title":"Automata, Languages and Programming","author":"N. Nisan","year":"2002","unstructured":"Nisan, N.: The communication complexity of approximate set packing and covering. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 868\u2013875. Springer, Heidelberg (2002)"},{"key":"33_CR12","doi-asserted-by":"crossref","unstructured":"Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multiparty communication complexity, made easy. In: Proc. of ACM-SIAM SODA, pp. 486\u2013501. SIAM (2012)","DOI":"10.1137\/1.9781611973099.42"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In: Proc. of ACM STOC, pp. 475\u2013484. ACM (1997)","DOI":"10.1145\/258533.258641"},{"key":"33_CR14","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 (2009)","DOI":"10.1137\/1.9781611972795.60"},{"key":"33_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-41527-2_2","volume-title":"Distributed Computing","author":"D.P. Woodruff","year":"2013","unstructured":"Woodruff, D.P., Zhang, Q.: When distributed computation is communication expensive. In: Afek, Y. (ed.) DISC 2013. LNCS, vol.\u00a08205, pp. 16\u201330. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-45174-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T05:31:53Z","timestamp":1650259913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-45174-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662451731","9783662451748"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-45174-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}