{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:34Z","timestamp":1781077534016,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642220111","type":"print"},{"value":"9783642220128","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22012-8_42","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T07:29:39Z","timestamp":1308382179000},"page":"526-538","source":"Crossref","is-referenced-by-count":17,"title":["Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem"],"prefix":"10.1007","author":[{"given":"Kook Jin","family":"Ahn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"42_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. LNCS, vol.\u00a05556, pp. 328\u2013338. Springer, Heidelberg (2009)"},{"key":"42_CR2","unstructured":"Ahn, K.J., Guha, S.: Laminar families and metric embeddings: Non-bipartite maximum matching problem in the semi-streaming model (manuscript, 2011), http:\/\/arxiv.org\/abs\/1104.4058"},{"key":"42_CR3","unstructured":"Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. To appear in the Proceedings of ICALP (2011), http:\/\/arxiv.org\/abs\/1104.2315"},{"key":"42_CR4","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta algorithm and applications (2005), http:\/\/www.cs.princeton.edu\/~arora\/pubs\/MWsurvey.pdf"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"Belkin, M., Niyogi, P.: Towards a theoretical foundation for laplacian based manifold methods. J. Comput. System Sci., 1289\u20131308 (2008)","DOI":"10.1016\/j.jcss.2007.08.006"},{"key":"42_CR6","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Approximating maximum weight matching in near-linear time. In: FOCS, pp. 673\u2013682 (2010)","DOI":"10.1109\/FOCS.2010.70"},{"key":"42_CR7","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards\u00a069, 125\u2013130 (1965)","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"42_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/978-3-642-04128-0_44","volume-title":"Algorithms - ESA 2009","author":"S. Eggert","year":"2009","unstructured":"Eggert, S., Kliemann, L., Srivastav, A.: Bipartite graph matchings in the semi-streaming model. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 492\u2013503. Springer, Heidelberg (2009)"},{"key":"42_CR9","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. In: Proc. of STACS, pp. 347\u2013358 (2010)"},{"issue":"2-3","key":"42_CR10","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":"42_CR11","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."},{"issue":"4","key":"42_CR12","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0895480199355754","volume":"13","author":"L.K. Fleischer","year":"2000","unstructured":"Fleischer, L.K.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discret. Math.\u00a013(4), 505\u2013520 (2000)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"42_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/jcss.1997.1504","volume":"55","author":"Y. Freund","year":"1997","unstructured":"Freund, Y., Schapire, R.E.: A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. (JCSS)\u00a055(1), 119\u2013139 (1997)","journal-title":"J. Comput. Syst. Sci. (JCSS)"},{"issue":"2","key":"42_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02579271","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z.: Maximum degree and fractional matchings in uniform hypergraphs. Combinatorica\u00a01(2), 155\u2013162 (1981)","journal-title":"Combinatorica"},{"issue":"2","key":"42_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01303202","volume":"13","author":"Z. F\u00fcredi","year":"1993","unstructured":"F\u00fcredi, Z., Kahn, J., Seymour, P.D.: On the fractional matching polytope of a hypergraph. Combinatorica\u00a013(2), 167\u2013180 (1993)","journal-title":"Combinatorica"},{"key":"42_CR16","unstructured":"Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: SODA, pp. 434\u2013443 (1990)"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proc. FOCS, pp. 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams (1998)","DOI":"10.1090\/dimacs\/050\/05"},{"issue":"4","key":"42_CR19","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n $^{\\mbox{5\/2}}$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"42_CR20","doi-asserted-by":"crossref","unstructured":"Jebara, T., Wang, J., Chang, S.-F.: Graph construction and b-matching for semi-supervised learning. In: Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, pp. 441\u2013448 (2009)","DOI":"10.1145\/1553374.1553432"},{"key":"42_CR21","unstructured":"Kalantari, B., Shokoufandeh, A.: Approximation schemes for maximum cardinality matching. Technical Report LCSR-TR-248, Laboratory for Computer Science Research, Department of Computer Science. Rutgers University (1995)"},{"key":"42_CR22","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":"42_CR23","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An ${O(\\sqrt{|V|}|E|)}$ algorithm for finding maximum matching in general graphs. In: FOCS, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"42_CR24","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science\u00a01(2) (2005)","DOI":"10.1561\/0400000002"},{"issue":"6","key":"42_CR25","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.ipl.2004.05.007","volume":"91","author":"S. Pettie","year":"2004","unstructured":"Pettie, S., Sanders, P.: A simpler linear time 2\/3-epsilon approximation for maximum weight matching. Inf. Process. Lett.\u00a091(6), 271\u2013276 (2004)","journal-title":"Inf. Process. Lett."},{"key":"42_CR26","doi-asserted-by":"crossref","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. In: FOCS, pp. 495\u2013504 (1991)","DOI":"10.1109\/SFCS.1991.185411"},{"key":"42_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-49116-3_24","volume-title":"STACS 99","author":"R. Preis","year":"1999","unstructured":"Preis, R.: Linear time 1\/2 -approximation algorithm for maximum weighted matching in general graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 259\u2013269. Springer, Heidelberg (1999)"},{"issue":"1","key":"42_CR28","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1077464.1077472","volume":"1","author":"D.E.D. Vinkemeier","year":"2005","unstructured":"Vinkemeier, D.E.D., Hougardy, S.: A linear-time approximation algorithm for weighted matchings in graphs. ACM Transactions on Algorithms\u00a01(1), 107\u2013122 (2005)","journal-title":"ACM Transactions on Algorithms"},{"key":"42_CR29","unstructured":"Young, N.E.: Randomized rounding without solving the linear program. In: Proc. SODA, pp. 170\u2013178 (1995)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22012-8_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T09:47:04Z","timestamp":1741254424000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22012-8_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220111","9783642220128"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22012-8_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}