{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:24Z","timestamp":1763468184945},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_38","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"453-464","source":"Crossref","is-referenced-by-count":8,"title":["Semi-Streaming Set Cover"],"prefix":"10.1007","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-02930-1_27","volume-title":"Automata, Languages and Programming","author":"K.J. Ahn","year":"2009","unstructured":"Ahn, K.J., Guha, S.: Graph sparsification in the semi-streaming model. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 328\u2013338. Springer, Heidelberg (2009)"},{"issue":"2","key":"38_CR2","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput.\u00a039(2), 361\u2013370 (2009)","journal-title":"SIAM J. Comput."},{"key":"38_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/978-3-642-31594-7_26","volume-title":"Automata, Languages, and Programming","author":"Y. Emek","year":"2012","unstructured":"Emek, Y., Halld\u00f3rsson, M.M., Ros\u00e9n, A.: Space-constrained interval selection. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 302\u2013313. Springer, Heidelberg (2012)"},{"key":"38_CR4","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. In: STACS, pp. 347\u2013358 (2010)"},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci.\u00a0348, 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"38_CR6","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/070683155","volume":"38","author":"J. Feigenbaum","year":"2008","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the data-stream model. SIAM J. Comput.\u00a038(5), 1709\u20131727 (2008)","journal-title":"SIAM J. Comput."},{"key":"38_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-40328-6_12","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P. Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Halld\u00f3rsson, M.M., Patt-Shamir, B., Rawitz, D., Ros\u00e9n, A.: Shrinking maxima, decreasing costs: New online packing and covering problems. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol.\u00a08096, pp. 158\u2013172. Springer, Heidelberg (2013)"},{"key":"38_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/978-3-642-14165-2_54","volume-title":"Automata, Languages and Programming","author":"B.V. Halld\u00f3rsson","year":"2010","unstructured":"Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Losievskaja, E., Szegedy, M.: Streaming algorithms for independent sets. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 641\u2013652. Springer, Heidelberg (2010)"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"38_CR10","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s00224-012-9396-1","volume":"53","author":"J.A. Kelner","year":"2013","unstructured":"Kelner, J.A., Levin, A.: Spectral sparsification in the semi-streaming setting. Theory Comput. Syst.\u00a053(2), 243\u2013262 (2013)","journal-title":"Theory Comput. Syst."},{"key":"38_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-642-32512-0_20","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C. Konrad","year":"2012","unstructured":"Konrad, C., Magniez, F., Mathieu, C.: Maximum matching in semi-streaming with few passes. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX 2012 and RANDOM 2012. LNCS, vol.\u00a07408, pp. 231\u2013242. Springer, Heidelberg (2012)"},{"key":"38_CR12","unstructured":"Lindner, C.C., Rodger, C.A.: Design Theory, 2nd edn. Discrete Mathematics and its Applications. CRC Press (2011)"},{"key":"38_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/11538462_15","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. McGregor","year":"2005","unstructured":"McGregor, A.: Finding graph matchings in data streams. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 170\u2013181. Springer, Heidelberg (2005)"},{"key":"38_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 2009, pp. 697\u2013708 (2009)","DOI":"10.1137\/1.9781611972795.60"},{"key":"38_CR15","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer-Verlag New York, Inc., New York (2001)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:09:27Z","timestamp":1558908567000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_38"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}