{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T15:43:37Z","timestamp":1767109417077},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"},{"type":"electronic","value":"9783540755203"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-75520-3_47","type":"book-chapter","created":{"date-parts":[[2007,9,13]],"date-time":"2007-09-13T23:46:33Z","timestamp":1189727193000},"page":"522-533","source":"Crossref","is-referenced-by-count":14,"title":["An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Niv","family":"Buchbinder","sequence":"additional","affiliation":[]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"47_CR1","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R.A. Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.: Searching in the plane. Information and Computation\u00a0106(2), 234\u2013252 (1993)","journal-title":"Information and Computation"},{"key":"47_CR2","first-page":"184","volume-title":"IEEE Symposium on Foundations of Computer Science","author":"Y. Bartal","year":"1996","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: IEEE Symposium on Foundations of Computer Science, pp. 184\u2013193. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"47_CR3","volume-title":"STOC: ACM Symposium on Theory of Computing (STOC)","author":"Y. Bartal","year":"1998","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: STOC: ACM Symposium on Theory of Computing (STOC), ACM Press, New York (1998)"},{"unstructured":"SBuchbinder, N., Jain, K., Naor, J.: The adauctions problem and extensions. In: ESA (to appear, 2007)","key":"47_CR4"},{"unstructured":"Chung, C., Pruhs, K., Uthaisombut, P.: The online transportation problem: On the exponential boost of one extra server. Under submission","key":"47_CR5"},{"key":"47_CR6","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1145\/780542.780608","volume-title":"STOC 2003","author":"J. Fakcharoenphol","year":"2003","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC 2003. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 448\u2013455. ACM Press, New York (2003)"},{"doi-asserted-by":"crossref","unstructured":"Fuchs, B., Hochstattler, W., Kern, W.: Online matching on a line. Theoretical Computer Science, 251\u2013264 (2005)","key":"47_CR7","DOI":"10.1016\/j.tcs.2004.10.028"},{"key":"47_CR8","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A General Approximation Technique for Constrained Forest Problems. SIAM Journal on Computing\u00a024, 296\u2013317 (1995)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"47_CR9","doi-asserted-by":"publisher","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\u00a014(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"key":"47_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029573","volume-title":"Online Algorithms","author":"B. Kalyanasundaram","year":"1998","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online network optimization problems, 1998. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms. LNCS, vol.\u00a01442, Springer, Heidelberg (1998)"},{"issue":"3","key":"47_CR11","doi-asserted-by":"publisher","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.\u00a013(3), 370\u2013383 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20132","key":"47_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.: An optimal deterministic algorithm for online b -matching. Theoretical Computer Science\u00a0233(1\u20132), 319\u2013325 (2000)","journal-title":"Theoretical Computer Science"},{"key":"47_CR13","first-page":"352","volume-title":"In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing","author":"R.M. Karp","year":"1990","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for online bipartite matching. In: In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 352\u2013358. ACM Press, New York (1990)"},{"issue":"2","key":"47_CR14","doi-asserted-by":"publisher","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.\u00a0127(2), 255\u2013267 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"47_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-3-540-24592-6_14","volume-title":"Approximation and Online Algorithms","author":"E. Koutsoupias","year":"2004","unstructured":"Koutsoupias, E., Nanavati, A.: The online matching problem on a line. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol.\u00a02909, pp. 179\u2013191. Springer, Heidelberg (2004)"},{"issue":"5","key":"47_CR16","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. Journal of the ACM\u00a042(5), 971\u2013983 (1995)","journal-title":"Journal of the ACM"},{"key":"47_CR17","first-page":"322","volume-title":"STOC: ACM Symposium on Theory of Computing","author":"M.S. Manasse","year":"1988","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for online problems. In: STOC: ACM Symposium on Theory of Computing, pp. 322\u2013333. ACM Press, New York (1988)"},{"key":"47_CR18","first-page":"264","volume-title":"IEEE Symposium on Foundations of Computer Science","author":"A. Mehta","year":"2005","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized on-line matching. In: IEEE Symposium on Foundations of Computer Science, pp. 264\u2013273. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"47_CR19","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1145\/1109557.1109662","volume-title":"SODA 2006","author":"A. Meyerson","year":"2006","unstructured":"Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: SODA 2006. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 954\u2013959. ACM Press, New York (2006)"},{"issue":"2","key":"47_CR20","doi-asserted-by":"publisher","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\u00a05(2), 163\u2013179 (1984)","journal-title":"J. Algorithms"},{"issue":"4","key":"47_CR21","doi-asserted-by":"publisher","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 Journal on Computing\u00a010(4), 676\u2013681 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"47_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.\u00a024. Springer, Berlin (2003)"},{"issue":"1","key":"47_CR23","doi-asserted-by":"publisher","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.\u00a012(1), 144\u2013156 (1983)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T10:22:19Z","timestamp":1558261339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540755197","9783540755203"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}