{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T02:11:54Z","timestamp":1777342314656,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_87","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T06:07:39Z","timestamp":1434694059000},"page":"1070-1081","source":"Crossref","is-referenced-by-count":39,"title":["Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm"],"prefix":"10.1007","author":[{"given":"Yajun","family":"Wang","sequence":"first","affiliation":[]},{"given":"Sam Chiu-wai","family":"Wong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"87_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"87_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-642-15781-3_19","volume-title":"Algorithms \u2013 ESA 2010","author":"N Bansal","year":"2010","unstructured":"Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 218\u2013229. Springer, Heidelberg (2010)"},{"issue":"1","key":"87_CR3","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/1360443.1360462","volume":"39","author":"B Birnbaum","year":"2008","unstructured":"Birnbaum, B., Mathieu, C.: On-line bipartite matching made simple. ACM SIGACT News 39(1), 80\u201387 (2008)","journal-title":"ACM SIGACT News"},{"issue":"5","key":"87_CR4","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1145\/1183907.1183913","volume":"53","author":"A Blum","year":"2006","unstructured":"Blum, A., Sandholm, T., Zinkevich, M.: Online algorithms for market clearing. Journal of the ACM (JACM) 53(5), 845\u2013879 (2006)","journal-title":"Journal of the ACM (JACM)"},{"key":"87_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-75520-3_24","volume-title":"Algorithms \u2013 ESA 2007","author":"N Buchbinder","year":"2007","unstructured":"Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 253\u2013264. Springer, Heidelberg (2007)"},{"issue":"1","key":"87_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2004.08.015","volume":"332","author":"M Demange","year":"2005","unstructured":"Demange, M., Paschos, V.T.: On-line vertex-covering. Theoretical Computer Science 332(1), 83\u2013108 (2005)","journal-title":"Theoretical Computer Science"},{"key":"87_CR7","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Huang, Z., Korula, N., Mirrokni, V.S., Yan, Q.: Whole-page optimization and submodular welfare maximization with online bidders. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 305\u2013322. ACM (2013)","DOI":"10.1145\/2492002.2482603"},{"key":"87_CR8","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 137\u2013144. ACM (2012)","DOI":"10.1145\/2213977.2213992"},{"key":"87_CR9","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of ranking for online bipartite matching. In: SODA 2013: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (to appear, 2013)"},{"key":"87_CR10","doi-asserted-by":"crossref","unstructured":"Devenur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: EC 2009: Proceedings of the Tenth ACM Conference on Electronic Commerce, pp. 71\u201378. ACM, New York (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"87_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-10841-9_34","volume-title":"Internet and Network Economics","author":"J Feldman","year":"2009","unstructured":"Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., P\u00e1l, M.: Online ad assignment with free disposal. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 374\u2013385. Springer, Heidelberg (2009)"},{"key":"87_CR12","doi-asserted-by":"crossref","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: Beating 1\u20131\/e. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 117\u2013126. IEEE (2009)","DOI":"10.1109\/FOCS.2009.72"},{"key":"87_CR13","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA, vol. 8, pp. 982\u2013991 (2008)"},{"issue":"1","key":"87_CR14","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 233(1), 319\u2013325 (2000)","journal-title":"Theoretical Computer Science"},{"key":"87_CR15","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 587\u2013596. ACM (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"87_CR16","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Kenyon, C., Randall, D.: Dynamic tcp acknowledgement and other stories about e\/(e-1). In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 502\u2013509. ACM (2001)","DOI":"10.1145\/380752.380845"},{"issue":"6","key":"87_CR17","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/BF01189993","volume":"11","author":"AR Karlin","year":"1994","unstructured":"Karlin, A.R., Manasse, M.S., McGeoch, L.A., Owicki, S.: Competitive randomized algorithms for nonuniform problems. Algorithmica 11(6), 542\u2013571 (1994)","journal-title":"Algorithmica"},{"issue":"1","key":"87_CR18","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3(1), 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"87_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 352\u2013358. ACM(1990)","DOI":"10.1145\/100216.100262"},{"key":"87_CR20","unstructured":"Lotker, Z., Patt-Shamir, B., Rawitz, D., Albers, S.: Rent, lease or buy: Randomized algorithms for multislope ski rental. In: 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), vol. 1 (2008)"},{"key":"87_CR21","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 597\u2013606. ACM (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"87_CR22","doi-asserted-by":"crossref","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: Online actions based on offline statistics. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1285\u20131294. SIAM (2011)","DOI":"10.1137\/1.9781611973082.98"},{"issue":"5","key":"87_CR23","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1284320.1284321","volume":"54","author":"A Mehta","year":"2007","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. Journal of the ACM (JACM) 54(5), 22 (2007)","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"87_CR24","first-page":"265","volume":"8","author":"A Mehta","year":"2012","unstructured":"Mehta, A.: Online matching and ad allocation. Theoretical Computer Science 8(4), 265\u2013368 (2012)","journal-title":"Theoretical Computer Science"}],"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-662-47672-7_87","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T03:01:41Z","timestamp":1559185301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_87","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}