{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T20:15:07Z","timestamp":1794341707963,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540380443","type":"print"},{"value":"9783540380450","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_44","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T08:33:54Z","timestamp":1156494834000},"page":"487-498","source":"Crossref","is-referenced-by-count":5,"title":["Fractional Matching Via Balls-and-Bins"],"prefix":"10.1007","author":[{"given":"Rajeev","family":"Motwani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rina","family":"Panigrahy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"44_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"44_CR2","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM Journal on Computing\u00a029, 180\u2013200 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"44_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-30140-0_7","volume-title":"Algorithms \u2013 ESA 2004","author":"Y. Azar","year":"2004","unstructured":"Azar, Y., Litichevskey, A.: Maximizing throughput in multi-queue switches. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 53\u201364. Springer, Heidelberg (2004)"},{"key":"44_CR4","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: The heavily loaded case. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 745\u2013754 (2000)","DOI":"10.1145\/335305.335411"},{"key":"44_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02186476","volume":"14","author":"D.P. Bertsekas","year":"1988","unstructured":"Bertsekas, D.P.: The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem. Annals of Operations Research\u00a014, 105\u2013123 (1988)","journal-title":"Annals of Operations Research"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Cherkassky, B.V., Goldberg, A.V., Martin, P., Setubal, J.C., Stolfi, J.: Augment or push: a computational study of bipartite matching and unit-capacity flow algorithms. ACM J. Exp. Algorithmics\u00a03 (1998)","DOI":"10.1145\/297096.297140"},{"key":"44_CR7","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"issue":"5","key":"44_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(92)90032-Q","volume":"42","author":"A.V. Goldberg","year":"1992","unstructured":"Goldberg, A.V.: A natural randomization strategy for multicommodity flow and related algorithms. Information Processing Letters\u00a042(5), 249\u2013256 (1992)","journal-title":"Information Processing Letters"},{"key":"44_CR10","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"Hopcroft, J., Karp, R.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing\u00a02, 225\u2013231 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"44_CR11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H.W. Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart.\u00a02, 83\u201397 (1955)","journal-title":"Naval Res. Logist. Quart."},{"key":"44_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(99)00140-1","volume":"233","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.R.: An optimal deterministic algorithm for online b-matching. Theoretical Computer Science\u00a0233, 319\u2013325 (2000)","journal-title":"Theoretical Computer Science"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for online bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (1990)","DOI":"10.1145\/100216.100262"},{"key":"44_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Matching Theory","author":"L. Lovasz","year":"1986","unstructured":"Lovasz, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics. North-Holland, Amsterdam (1986)"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Motwani, R., Panigrahy, R., Xu, Y.: Fraction Matching via Balls-and-Bins. Technical Report (2005)","DOI":"10.1007\/11830924_44"},{"key":"44_CR16","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: AdWords and Generalized On-line Matching. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (2005)","DOI":"10.1109\/SFCS.2005.12"},{"key":"44_CR17","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.: An $O(E\\sqrt V)$ algorithm for finding maximum matchings in general graphs. In: Proceedings of the 21st IEEE Symposium on the Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"44_CR18","unstructured":"Panigrahy, R.: Efficient Hashing with Lookups in Two Memory Accesses. In: Proceedings of SODA (2005)"},{"key":"44_CR19","doi-asserted-by":"crossref","unstructured":"Plotkin, S.A., Shmoys, D., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. In: Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science (1991)","DOI":"10.1109\/SFCS.1991.185411"},{"key":"44_CR20","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0020-0190(00)00073-9","volume":"75","author":"M. Penn","year":"2000","unstructured":"Penn, M., Tennenholtz, M.: Constrained multi-object auctions and b-matching. Information Processing Letters\u00a075, 29\u201334 (2000)","journal-title":"Information Processing Letters"},{"key":"44_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/3-540-49543-6_13","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M. Raab","year":"1998","unstructured":"Raab, M., Steger, A.: Balls into bins \u2013 a simple and tight analysis. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol.\u00a01518, pp. 159\u2013170. Springer, Heidelberg (1998)"},{"key":"44_CR22","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0004-3702(02)00229-1","volume":"140","author":"M. Tennenholtz","year":"2002","unstructured":"Tennenholtz, M.: Tractable combinatorial auctions and b-matching. Artif. Intell.\u00a0140, 231\u2013243 (2002)","journal-title":"Artif. Intell."}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T10:29:22Z","timestamp":1736504962000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11830924_44","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11830924","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}