{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:51Z","timestamp":1763468271083,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_23","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"263-274","source":"Crossref","is-referenced-by-count":20,"title":["Sublinear Estimation of Weighted Matchings in Dynamic Data Streams"],"prefix":"10.1007","author":[{"given":"Marc","family":"Bury","sequence":"first","affiliation":[]},{"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"23_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. Ahn","year":"2009","unstructured":"Ahn, K., 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)"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Ahn, K., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: SODA, pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Ahn, K., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: PODS, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-40328-6_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K. Ahn","year":"2013","unstructured":"Ahn, K., Guha, S., McGregor, A.: Spectral sparsification in dynamic graph streams. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol.\u00a08096, pp. 1\u201310. Springer, Heidelberg (2013)"},{"key":"23_CR5","unstructured":"Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Tight bounds for linear sketches of approximate matchings. CoRR, abs\/1505.01467 (2015)"},{"issue":"1","key":"23_CR6","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1137\/060651835","volume":"38","author":"Z. Bar-Yossef","year":"2008","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kerenidis, I.: Exponential separation of quantum and classical one-way communication complexity. SIAM J. Comput.\u00a038(1), 366\u2013384 (2008)","journal-title":"SIAM J. Comput."},{"key":"23_CR7","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to dynamic graph streams. CoRR, abs\/1505.01731 (2015)"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Clarkson, K., Woodruff, D.: Numerical linear algebra in the streaming model. In: STOC, pp. 205\u2013214 (2009)","DOI":"10.1145\/1536414.1536445"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-642-40450-4_29","volume-title":"Algorithms \u2013 ESA 2013","author":"M. Crouch","year":"2013","unstructured":"Crouch, M., McGregor, A., Stubbs, D.: Dynamic graphs in the sliding-window model. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 337\u2013348. Springer, Heidelberg (2013)"},{"key":"23_CR10","unstructured":"Crouch, M., Stubbs, D.: Improved streaming algorithms for weighted matching, via unweighted matching. In: APPROX\/RANDOM 2014, pp. 96\u2013104 (2014)"},{"issue":"3","key":"23_CR11","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L. Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discrete Math.\u00a025(3), 1251\u20131265 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"23_CR12","unstructured":"Epstein, L., Levin, A., Segev, D., Weimann, O.: Improved bounds for online preemptive matching. In: STACS, pp. 389\u2013399 (2013)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Esfandiari, H., Hajiaghayi, M., Liaghat, V., Monemizadeh, M., Onak, K.: Streaming algorithms for estimating the matching size in planar graphs and beyond. In: SODA, pp. 1217\u20131233 (2015)","DOI":"10.1137\/1.9781611973730.81"},{"issue":"2-3","key":"23_CR14","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(2-3), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"23_CR15","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1137\/070706550","volume":"38","author":"D. Gavinsky","year":"2008","unstructured":"Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., de Wolf, R.: Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput.\u00a038(5), 1695\u20131708 (2008)","journal-title":"SIAM J. Comput."},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Goel, A., Kapralov, M., Khanna, S.: On the communication and streaming complexity of maximum bipartite matching. In: SODA, pp. 468\u2013485 (2012)","DOI":"10.1137\/1.9781611973099.41"},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams (1998)","DOI":"10.1090\/dimacs\/050\/05"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings and data stream computation. In: FOCS, pp. 189\u2013197 (2000)","DOI":"10.1109\/SFCS.2000.892082"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Kapralov, M.: Better bounds for matchings in the streaming model. In: SODA, pp. 1679\u20131697 (2013)","DOI":"10.1137\/1.9781611973105.121"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Khanna, S., Sudan, M.: Approximating matching size from random streams. In: SODA, pp. 734\u2013751 (2014)","DOI":"10.1137\/1.9781611973402.55"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Konrad, C.: Maximum matching in turnstile streams. CoRR, abs\/1505.01460 (2015)","DOI":"10.1007\/978-3-662-48350-3_70"},{"key":"23_CR22","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":"23_CR23","doi-asserted-by":"crossref","unstructured":"Li, Y., Nguyen, H., Woodruff, D.: On sketching matrix norms and the top singular vector. In: SODA, pp. 1562\u20131581 (2014)","DOI":"10.1137\/1.9781611973402.114"},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Li, Y., Nguyen, H., Woodruff, D.: Turnstile streaming algorithms might as well be linear sketches. In: STOC, pp. 174\u2013183 (2014)","DOI":"10.1145\/2591796.2591812"},{"key":"23_CR25","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: FCT, pp. 565\u2013574 (1979)"},{"key":"23_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"issue":"1","key":"23_CR27","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\u00a043(1), 9\u201320 (2014)","journal-title":"SIGMOD Record"},{"issue":"4","key":"23_CR28","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica\u00a012(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"key":"23_CR29","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W. Tutte","year":"1947","unstructured":"Tutte, W.: The factorization of linear graphs. J. London Math. Soc.\u00a022, 107\u2013111 (1947)","journal-title":"J. London Math. Soc."},{"issue":"1-2","key":"23_CR30","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0190(00)00128-9","volume":"76","author":"R. Uehara","year":"2000","unstructured":"Uehara, R., Chen, Z.: Parallel approximation algorithms for maximum weighted matching in general graphs. Inf. Process. Lett.\u00a076(1-2), 13\u201317 (2000)","journal-title":"Inf. Process. Lett."},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"Verbin, E., Yu, W.: The streaming complexity of cycle counting, sorting by reversals, and other problems. In: SODA, pp. 11\u201325. SIAM (2011)","DOI":"10.1137\/1.9781611973082.2"},{"issue":"1-2","key":"23_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-010-9438-5","volume":"62","author":"M. Zelke","year":"2012","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. Algorithmica\u00a062(1-2), 1\u201320 (2012)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T09:57:16Z","timestamp":1748599036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}