{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T01:56:55Z","timestamp":1768269415422,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,8,4]],"date-time":"2012-08-04T00:00:00Z","timestamp":1344038400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00453-012-9676-9","type":"journal-article","created":{"date-parts":[[2012,8,3]],"date-time":"2012-08-03T14:32:03Z","timestamp":1344004323000},"page":"390-403","source":"Crossref","is-referenced-by-count":38,"title":["A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching"],"prefix":"10.1007","volume":"68","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niv","family":"Buchbinder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,4]]},"reference":[{"issue":"2","key":"9676_CR1","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R.A. Baeza-Yates","year":"1991","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. Comput. 106(2), 234\u2013252 (1991)","journal-title":"Inf. Comput."},{"key":"9676_CR2","first-page":"184","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"Y. Bartal","year":"1996","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: 37th Annual Symposium on Foundations of Computer Science, pp. 184\u2013193 (1996)"},{"key":"9676_CR3","first-page":"161","volume-title":"Proceedings of the 30th Annual ACM Symposium on Theory of Computing","author":"Y. Bartal","year":"1998","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 161\u2013168 (1998)"},{"key":"9676_CR4","first-page":"253","volume-title":"European Symposium on Algorithms (ESA)","author":"N. Buchbinder","year":"2007","unstructured":"Buchbinder, N., Jain, K., Naor, J.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: European Symposium on Algorithms (ESA), pp. 253\u2013264 (2007)"},{"key":"9676_CR5","first-page":"228","volume-title":"Latin American Theoretical Informatics (LATIN)","author":"C. Chung","year":"2008","unstructured":"Chung, C., Pruhs, K., Uthaisombut, P.: The online transportation problem: on the exponential boost of one extra server. In: Latin American Theoretical Informatics (LATIN), pp. 228\u2013239 (2008)"},{"issue":"3","key":"9676_CR6","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"9676_CR7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.tcs.2004.10.028","volume":"332","author":"B. Fuchs","year":"2005","unstructured":"Fuchs, B., Hochst\u00e4ttler, W., Kern, W.: Online matching on a line. Theor. Comput. Sci. 332(1\u20133), 251\u2013264 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9676_CR8","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. Goemans","year":"1992","unstructured":"Goemans, M., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296\u2013317 (1992)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9676_CR9","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B. Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"key":"9676_CR10","first-page":"268","volume-title":"Online Algorithms","author":"B. Kalyanasundaram","year":"1996","unstructured":"Kalyanasundaram, B., Pruhs, K.: On-line network optimization problems. In: Online Algorithms, pp. 268\u2013280 (1996)"},{"issue":"3","key":"9676_CR11","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1137\/S0895480198342310","volume":"13","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: The online transportation problem. SIAM J. Discrete Math. 13(3), 370\u2013383 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20132","key":"9676_CR12","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/S0304-3975(99)00140-1","volume":"233","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci. 233(1\u20132), 319\u2013325 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9676_CR13","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1145\/100216.100262","volume-title":"STOC","author":"R.M. Karp","year":"1990","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: STOC, pp. 352\u2013358 (1990)"},{"issue":"2","key":"9676_CR14","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9676_CR15","first-page":"179","volume-title":"Workshop on Approximation and Online Algorithms","author":"E. Koutsoupias","year":"2003","unstructured":"Koutsoupias, E., Nanavati, A.: The online matching problem on a line. In: Workshop on Approximation and Online Algorithms, pp. 179\u2013191 (2003)"},{"issue":"5","key":"9676_CR16","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM 42(5), 971\u2013983 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"9676_CR17","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M.S. Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208\u2013230 (1990)","journal-title":"J. Algorithms"},{"key":"9676_CR18","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54(5) (2007)","DOI":"10.1145\/1284320.1284321"},{"key":"9676_CR19","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1145\/1109557.1109662","volume-title":"SODA \u201906","author":"A. Meyerson","year":"2006","unstructured":"Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: SODA \u201906, pp. 954\u2013959 (2006)"},{"issue":"2","key":"9676_CR20","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0196-6774(84)90024-5","volume":"5","author":"D.A. Plaisted","year":"1984","unstructured":"Plaisted, D.A.: Heuristic matching for graphs satisfying the triangle inequality. J. Algorithms 5(2), 163\u2013179 (1984)","journal-title":"J. Algorithms"},{"issue":"4","key":"9676_CR21","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0210050","volume":"10","author":"E.M. Reingold","year":"1981","unstructured":"Reingold, E.M., Tarjan, R.E.: On a greedy heuristic for complete matching. SIAM J. Comput. 10(4), 676\u2013681 (1981)","journal-title":"SIAM J. Comput."},{"key":"9676_CR22","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"issue":"1","key":"9676_CR23","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1137\/0212009","volume":"12","author":"K.J. Supowit","year":"1983","unstructured":"Supowit, K.J., Reingold, E.M., Plaisted, D.A.: The travelling salesman problem and minimum matching in the unit square. SIAM J. Comput. 12(1), 144\u2013156 (1983)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9676-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9676-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9676-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T09:59:26Z","timestamp":1562061566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9676-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,4]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9676"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9676-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,4]]}}}