{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T08:06:58Z","timestamp":1767773218363},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_55","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"653-664","source":"Crossref","is-referenced-by-count":20,"title":["Converting Online Algorithms to Local Computation Algorithms"],"prefix":"10.1007","author":[{"given":"Yishay","family":"Mansour","sequence":"first","affiliation":[]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[]},{"given":"Shai","family":"Vardi","sequence":"additional","affiliation":[]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1132\u20131139 (2012)","DOI":"10.1137\/1.9781611973099.89"},{"issue":"1","key":"55_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(1), 180\u2013200 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"55_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the Lov\u00e1sz Local Lemma. Random Structures and Algorithms\u00a02, 343\u2013365 (1991)","journal-title":"Random Structures and Algorithms"},{"key":"55_CR4","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Brinkmann, A., Friedetzky, T., Nagel, L.: Balls into non-uniform bins. In: Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1\u201310. IEEE (2010)","DOI":"10.1109\/IPDPS.2010.5470355"},{"issue":"6","key":"55_CR5","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1137\/S009753970444435X","volume":"35","author":"P. Berenbrink","year":"2006","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: The heavily loaded case. SIAM J. Comput.\u00a035(6), 1350\u20131385 (2006)","journal-title":"SIAM J. Comput."},{"key":"55_CR6","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"key":"55_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-540-45172-3_7","volume-title":"Peer-to-Peer Systems II","author":"J.W. Byers","year":"2003","unstructured":"Byers, J.W., Considine, J., Mitzenmacher, M.: Simple Load Balancing for Distributed Hash Tables. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol.\u00a02735, pp. 80\u201388. Springer, Heidelberg (2003)"},{"key":"55_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D. Dubhashi","year":"1996","unstructured":"Dubhashi, D., Ranjan, D.: Balls and bins: A study in negative dependence. Random Structures and Algorithms\u00a013, 99\u2013124 (1996)","journal-title":"Random Structures and Algorithms"},{"key":"55_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/11830924_43","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Marko","year":"2006","unstructured":"Marko, S., Ron, D.: Distance Approximation in Bounded-Degree and General Sparse Graphs. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 475\u2013486. Springer, Heidelberg (2006)"},{"key":"55_CR10","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/978-1-4615-0013-1_9","volume-title":"Handbook of Randomized Computing","author":"M. Mitzenmacher","year":"2001","unstructured":"Mitzenmacher, M., Richa, A., Sitaraman, R.: The power of two random choices: A survey of techniques and results. In: Pardalos, P., Rajasekaran, S., Reif, J., Rolim, J. (eds.) Handbook of Randomized Computing, vol.\u00a0I, pp. 255\u2013312. Kluwer Academic Publishers, Norwell (2001)"},{"key":"55_CR11","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"55_CR12","doi-asserted-by":"crossref","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science\u00a0381(1\u20133) (2007)","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"55_CR13","unstructured":"Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: Proc. 2nd Symposium on Innovations in Computer Science, pp. 223\u2013238 (2011)"},{"key":"55_CR14","doi-asserted-by":"crossref","unstructured":"Talwar, K., Wieder, U.: Balanced allocations: the weighted case. In: Proc. 39th Annual ACM Symposium on the Theory of Computing, pp. 256\u2013265 (2007)","DOI":"10.1145\/1250790.1250829"},{"key":"55_CR15","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1145\/792538.792546","volume":"50","author":"B. V\u00f6cking","year":"2003","unstructured":"V\u00f6cking, B.: How asymmetry helps load balancing. J. ACM\u00a050, 568\u2013589 (2003)","journal-title":"J. ACM"},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Yamamoto, Y., Ito, H.: An improved constant-time approximation algorithm for maximum matchings. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 225\u2013234 (2009)","DOI":"10.1145\/1536414.1536447"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T00:53:33Z","timestamp":1558313613000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}