{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:13:40Z","timestamp":1759335220247},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_25","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"291-302","source":"Crossref","is-referenced-by-count":5,"title":["On Randomized Online Labeling with Polynomially Many Labels"],"prefix":"10.1007","author":[{"given":"Jan","family":"Bul\u00e1nek","sequence":"first","affiliation":[]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/227595.227596","volume":"43","author":"Y. Afek","year":"1996","unstructured":"Afek, Y., Awerbuch, B., Plotkin, S., Saks, M.: Local management of a global resource in a communication network. J. ACM\u00a043(1), 1\u201319 (1996)","journal-title":"J. ACM"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-33090-2_12","volume-title":"Algorithms \u2013 ESA 2012","author":"M. Babka","year":"2012","unstructured":"Babka, M., Bul\u00e1nek, J., \u010cun\u00e1t, V., Kouck\u00fd, M., Saks, M.: On Online Labeling with Polynomially Many Labels. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 121\u2013132. Springer, Heidelberg (2012)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-45749-6_17","volume-title":"Algorithms - ESA 2002","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 152\u2013164. Springer, Heidelberg (2002)"},{"issue":"2","key":"25_CR4","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/S0097539701389956","volume":"35","author":"M. Bender","year":"2005","unstructured":"Bender, M., Demaine, E., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput.\u00a035(2), 341\u2013358 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"25_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jalgor.2004.04.014","volume":"53","author":"M. Bender","year":"2004","unstructured":"Bender, M., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. J. Algorithms\u00a053(2), 115\u2013136 (2004)","journal-title":"J. Algorithms"},{"issue":"1","key":"25_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.ipl.2006.07.011","volume":"101","author":"R. Bird","year":"2007","unstructured":"Bird, R., Sadnicki, S.: Minimal on-line labelling. Inf. Process. Lett.\u00a0101(1), 41\u201345 (2007)","journal-title":"Inf. Process. Lett."},{"key":"25_CR7","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998)"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Brodal, G., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: SODA, pp. 39\u201348 (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Bul\u00e1nek, J., Kouck\u00fd, M., Saks, M.: Tight lower bounds for online labeling problem. In: STOC, pp. 1185\u20131198 (2012)","DOI":"10.1145\/2213977.2214083"},{"issue":"3","key":"25_CR10","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1137\/S0895480100315808","volume":"18","author":"P. Dietz","year":"2004","unstructured":"Dietz, P., Seiferas, J., Zhang, J.: A tight lower bound for online monotonic list labeling. SIAM J. Discrete Math.\u00a018(3), 626\u2013637 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/3-540-52846-6_87","volume-title":"SWAT \u201990","author":"P. Dietz","year":"1990","unstructured":"Dietz, P., Zhang, J.: Lower bounds for monotonic list labeling. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 173\u2013180. Springer, Heidelberg (1990)"},{"issue":"3-4","key":"25_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00446-010-0119-z","volume":"24","author":"Y. Emek","year":"2011","unstructured":"Emek, Y., Korman, A.: New bounds for the controller problem. Distributed Computing\u00a024(3-4), 177\u2013186 (2011)","journal-title":"Distributed Computing"},{"key":"25_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-10843-2_34","volume-title":"Automata, Languages and Programming","author":"A. Itai","year":"1981","unstructured":"Itai, A., Konheim, A., Rodeh, M.: A sparse table implementation of priority queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol.\u00a0115, pp. 417\u2013431. Springer, Heidelberg (1981)"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S.: Controller and estimator for dynamic networks. In: PODC, pp. 175\u2013184 (2007)","DOI":"10.1145\/1281100.1281127"},{"issue":"2","key":"25_CR15","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0890-5401(92)90034-D","volume":"97","author":"D. Willard","year":"1992","unstructured":"Willard, D.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Inf. Comput.\u00a097(2), 150\u2013204 (1992)","journal-title":"Inf. Comput."},{"key":"25_CR16","unstructured":"Zhang, J.: Density Control and On-Line Labeling Problems. PhD thesis, University of Rochester (1993)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:18:21Z","timestamp":1557911901000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}