{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:18:33Z","timestamp":1773796713073,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642041273","type":"print"},{"value":"9783642041280","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_46","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"516-527","source":"Crossref","is-referenced-by-count":12,"title":["Hyperbolic Dovetailing"],"prefix":"10.1007","author":[{"given":"David","family":"Kirkpatrick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"46_CR1","unstructured":"Azar, Y., Broder, A.Z., Manasse, M.S.: On-line choice of on-line algorithms. In: Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 432\u2013440 (1993)"},{"issue":"2","key":"46_CR2","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.E.: Searching in the plane. Information and Computation\u00a0106(2), 234\u2013252 (1993)","journal-title":"Information and Computation"},{"key":"46_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica\u00a011, 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"46_CR4","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. ACM Trans. on Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240245"},{"key":"46_CR5","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst order ratio applied to paging. In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 718\u2013727 (2005)"},{"key":"46_CR6","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"E. Demaine","year":"2006","unstructured":"Demaine, E., Fekete, S., Gal, S.: Online searching with turn cost. Theoretical Computer Science\u00a0361, 342\u2013355 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"46_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/1086649.1086670","volume":"36","author":"R. Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., Lopez-Ortiz, A.: A survey of performance measures for on-line algorithms. ACM SIGACT News\u00a036(3), 67\u201381 (2005)","journal-title":"ACM SIGACT News"},{"key":"46_CR8","unstructured":"Kao, M.-Y., Littman, M.L.: Algorithms for informed cows. In: AAAI 1997 Workshop on On-Line Search (1997)"},{"issue":"1","key":"46_CR9","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0959","volume":"29","author":"M.-Y. Kao","year":"1998","unstructured":"Kao, M.-Y., Ma, Y., Sipser, M., Yin, Y.: Optimal constructions of hybrid algorithms. J. Algorithms\u00a029(1), 142\u2013164 (1998)","journal-title":"J. Algorithms"},{"issue":"1","key":"46_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M.-Y. Kao","year":"1996","unstructured":"Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation\u00a0131(1), 63\u201379 (1996)","journal-title":"Information and Computation"},{"key":"46_CR11","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 359\u2013364 (1996)"},{"key":"46_CR12","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C., Yannakakis, M.: Searching a fixed graph. In: Proc. 23rd International Colloquium on Automata, Languages and Programming, pp. 280\u2013289 (1996)","DOI":"10.1007\/3-540-61440-0_135"},{"issue":"28","key":"46_CR13","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/S0304-3975(00)00144-4","volume":"2","author":"A. Lopez-Ortiz","year":"2001","unstructured":"Lopez-Ortiz, A., Schuierer, S.: The ultimate strategy to search on m rays. Theoretical Computer Science\u00a02(28), 267\u2013295 (2001)","journal-title":"Theoretical Computer Science"},{"key":"46_CR14","doi-asserted-by":"crossref","unstructured":"Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of Las Vegas algorithms. In: Proc. Second Israel Symposium on Theory of Computing and Systems, June 1993, pp. 128\u2013133 (1993)","DOI":"10.1109\/ISTCS.1993.253477"},{"key":"46_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest path without a map. In: Proc. 16th International Colloquium on Automata, Languages and Programming, pp. 610\u2013620 (1989)","DOI":"10.1007\/BFb0035787"},{"key":"46_CR16","doi-asserted-by":"crossref","unstructured":"Schonhage, A.: Adaptive raising strategies optimizing relative efficiency. In: Proc. 30th International Colloquium on Automata, Languages and Programming, pp. 611\u2013623 (2003)","DOI":"10.1007\/3-540-45061-0_49"},{"issue":"1","key":"46_CR17","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0925-7721(00)00030-4","volume":"18","author":"S. Schuierer","year":"2001","unstructured":"Schuierer, S.: Lower bounds in on-line geometric searching. Computational Geometry: Theory and Applications\u00a018(1), 37\u201353 (2001)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"46_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/3-540-36477-3_20","volume-title":"Computer Science in Perspective","author":"S. Schuierer","year":"2003","unstructured":"Schuierer, S.: A lower bound for randomized searching on m rays. In: Klein, R., Six, H.-W., Wegner, L. (eds.) Computer Science in Perspective. LNCS, vol.\u00a02598, pp. 264\u2013277. Springer, Heidelberg (2003)"},{"key":"46_CR19","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Comm. ACM, 202\u2013208 (February 1985)","DOI":"10.1145\/2786.2793"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T14:38:33Z","timestamp":1552142313000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}