{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:22Z","timestamp":1759638862784},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_16","type":"book-chapter","created":{"date-parts":[[2013,8,10]],"date-time":"2013-08-10T01:20:34Z","timestamp":1376097634000},"page":"236-250","source":"Crossref","is-referenced-by-count":7,"title":["In Pursuit of the Dynamic Optimality Conjecture"],"prefix":"10.1007","author":[{"given":"John","family":"Iacono","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"16_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S. Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing\u00a08(1), 121\u2013164 (2012)","journal-title":"Theory of Computing"},{"issue":"4","key":"16_CR2","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1145\/322092.322094","volume":"25","author":"B. Allenand","year":"1978","unstructured":"Allenand, B., Ian Munro, J.: Self-organizing binary search trees. J. ACM\u00a025(4), 526\u2013535 (1978)","journal-title":"J. ACM"},{"issue":"2","key":"16_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2007.03.002","volume":"382","author":"M. Badoiu","year":"2007","unstructured":"Badoiu, M., Cole, R., Demaine, E.D., Iacono, J.: A unified access bound on comparison-based dynamic dictionaries. Theor. Comput. Sci.\u00a0382(2), 86\u201396 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-31594-7_11","volume-title":"Automata, Languages, and Programming","author":"P. Bose","year":"2012","unstructured":"Bose, P., Collette, S., Fagerberg, R., Langerman, S.: De-amortizing binary search trees. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 121\u2013132. Springer, Heidelberg (2012)"},{"issue":"3","key":"16_CR5","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00453-003-1015-8","volume":"36","author":"A. Blum","year":"2003","unstructured":"Blum, A., Chawla, S., Kalai, A.: Static optimality and dynamic search-optimality in lists and trees. Algorithmica\u00a036(3), 249\u2013260 (2003)","journal-title":"Algorithmica"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Bose, P., Dou\u00efeb, K., Iacono, J., Langerman, S.: The power and limitations of static binary search trees with lazy finger. CoRR, abs\/1304.6897 (2013)","DOI":"10.1007\/978-3-319-13075-0_15"},{"issue":"1","key":"16_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539797326988","volume":"30","author":"R. Cole","year":"2000","unstructured":"Cole, R., Mishra, B., Schmidt, J.P., Siegel, A.: On the dynamic finger conjecture for splay trees. part i: Splay sorting log n-block sequences. SIAM J. Comput.\u00a030(1), 1\u201343 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"16_CR8","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/S009753979732699X","volume":"30","author":"R. Cole","year":"2000","unstructured":"Cole, R.: On the dynamic finger conjecture for splay trees. part ii: The proof. SIAM J. Comput.\u00a030(1), 44\u201385 (2000)","journal-title":"SIAM J. Comput."},{"key":"16_CR9","unstructured":"Derryberry, J.: Adaptive Binary Search Trees. PhD thesis, CMU (2009)"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Harmon, D., Iacono, J., Kane, D.M., Patrascu, M.: The geometry of binary search trees. In: Mathieu, C. (ed.) SODA, pp. 496\u2013505. SIAM (2009)","DOI":"10.1137\/1.9781611973068.55"},{"issue":"1","key":"16_CR11","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/S0097539705447347","volume":"37","author":"E.D. Demaine","year":"2007","unstructured":"Demaine, E.D., Harmon, D., Iacono, J., Patrascu, M.: Dynamic optimality - almost. SIAM J. Comput.\u00a037(1), 240\u2013251 (2007)","journal-title":"SIAM J. Comput."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Iacono, J., Langerman, S., \u00d6zkan, \u00d6.: Combining binary search trees. CoRR, abs\/1304.7604 (2013)","DOI":"10.1007\/978-3-642-39206-1_33"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-03367-4_18","volume-title":"Algorithms and Data Structures","author":"J.C. Derryberry","year":"2009","unstructured":"Derryberry, J.C., Sleator, D.D.: Skip-splay: Toward achieving the unified bound in the bst model. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 194\u2013205. Springer, Heidelberg (2009)"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-22300-6_35","volume-title":"Algorithms and Data Structures","author":"K. Fox","year":"2011","unstructured":"Fox, K.: Upper bounds for maximally greedy binary search trees. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 411\u2013422. Springer, Heidelberg (2011)"},{"key":"16_CR15","unstructured":"Harmon, D.: New Bounds on Optimal Binary Search Trees. PhD thesis, MIT (2006)"},{"key":"16_CR16","unstructured":"Lucas, J.M.: Canonical forms for competitive binary search tree algorithms. Technical Report DCS-TR-250, Rutgers University (1988)"},{"key":"16_CR17","unstructured":"Sleator, D.: Achieving the unified bound in the bst model. In: 5th Bertinoro Workshop on Algorithms and Data Structures. Talk (2011)"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"3","key":"16_CR19","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM\u00a032(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"issue":"3","key":"16_CR20","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jagm.1996.0025","volume":"20","author":"A. Subramanian","year":"1996","unstructured":"Subramanian, A.: An explanation of splaying. J. Algorithms\u00a020(3), 512\u2013525 (1996)","journal-title":"J. Algorithms"},{"issue":"1","key":"16_CR21","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0218004","volume":"18","author":"R.E. Wilber","year":"1989","unstructured":"Wilber, R.E.: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput.\u00a018(1), 56\u201367 (1989)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T15:23:27Z","timestamp":1558020207000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}