Top

Published in:

2018 | OriginalPaper | Chapter

Online Labeling: Algorithms, Lower Bounds and Open Questions

Author : Michael Saks

Published in: Computer Science – Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The online labeling problem (also known as the file maintenance problem), is a natural algorithmic problem that has arisen as a buidling block for data structures. A stream of distinct integer items is to be assigned labels online from a label set \(\{1,\ldots ,m\}\) so that the order of the labels respects the natural order of the items. Maintaining order on the labels may require relabeling items. The algorithm pays 1 each time an item is labeled or relabeled and the goal of the algorithm is to minimize the total cost.

We survey upper and lower bounds and open problems in both the deterministic and randomized setting.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Lower Bounds for Unrestricted Boolean Circuits: Open Problems

next chapter Maintaining Chordal Graphs Dynamically: Improved Upper and Lower Bounds

Afek, Y., Awerbuch, B., Plotkin, S.A., Saks, M.E.: Local management of a global resource in a communication network. J. ACM 43(1), 1–19 (1996)MathSciNetCrossRefMATH

Babka, M., Bulánek, J., Čunát, V., Koucký, M., Saks, M.: On online labeling with polynomially many labels. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 121–132. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33090-2_12CrossRef

Babka, M., Bulánek, J., Čunát, V., Koucký, M., Saks, M.: On online labeling with large label set. SIAM J. Disc. Math. (2017, to appear). http://sites.math.rutgers.edu/~saks/PUBS/large-label.pdf

Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: Möhring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 152–164. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45749-6_17CrossRefMATH

Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 35(2), 341–358 (2005). https://doi.org/10.1137/S0097539701389956MathSciNetCrossRefMATH

Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. J. Algorithms 53(2), 115–136 (2004). https://doi.org/10.1016/j.jalgor.2004.04.014MathSciNetCrossRefMATH

Bird, R.S., Sadnicki, S.: Bird and Stefan Sadnicki: minimal on-line labelling. Inf. Process. Lett. 101(1), 41–45 (2007). https://doi.org/10.1016/j.ipl.2006.07.011CrossRefMATH

Brodal, G.S., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 39–48. Society for Industrial and Applied Mathematics (2002) http://dl.acm.org/citation.cfm?id=545381.545386

Bulánek, J., Koucký, M., Saks, M.: Tight lower bounds for the online labeling problem. SIAM J. Comput. 44(6), 1765–1797 (2015). https://doi.org/10.1145/2213977.2214083. (Preliminary version: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC 2012, pp. 1185–1198. ACM, New York (2012))MathSciNetCrossRefMATH

10.

Bulánek, J., Koucký, M., Saks, M.: On randomized online labeling with polynomially many labels. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 291–302. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39206-1_25CrossRef

11.

Dietz, P.F.: Maintaining order in a linked list. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC, pp. 122–127 (1982)

12.

Dietz, P.F., Seiferas, J.I., Zhang, J.: Lower bounds for smooth list labeling. Manuscript (2005). (Listed in the references of [13])

13.

Dietz, P.F., Seiferas, J.I., Zhang, J.: A tight lower bound for online monotonic list labeling. SIAM J. Discret. Math. 18, 626–637 (2005)MathSciNetCrossRefMATH

14.

Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 365–372, ACM, New York (1987). https://doi.org/10.1145/28395.28434

15.

Dietz, P.F., Zhang, J.: Lower bounds for monotonic list labeling. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol. 447, pp. 173–180. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-52846-6_87CrossRef

16.

Emek, Y., Korman, A.: New bounds for the controller problem. Distrib. Comput. 24(3–4), 177–186 (2011). https://doi.org/10.1007/s00446-010-0119-zCrossRefMATH

17.

Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 417–431. Springer, Heidelberg (1981). https://doi.org/10.1007/3-540-10843-2_34CrossRef

18.

Korman, A., Kutten, S.: Controller and estimator for dynamic networks. In: PODC, pp. 175–184 (2007)

19.

Kopelowitz, T.: On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS 2012, Washington, DC, USA, pp. 283–292. IEEE Computer Society (2012). https://doi.org/10.1109/FOCS.2012.79

20.

Willard, D.E.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time. Inf. Comput. 97(2), 150–204 (1992). https://doi.org/10.1016/0890-5401(92)90034-DMathSciNetCrossRefMATH

21.

Zhang, J.: Density control and on-line labeling problems. Ph.D. thesis, University of Rochester, Rochester (1993)

Title: Online Labeling: Algorithms, Lower Bounds and Open Questions
Author: Michael Saks
Publisher: Springer International Publishing
Book: Computer Science – Theory and Applications
Print ISBN: 978-3-319-90529-7

Electronic ISBN: 978-3-319-90530-3

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-90530-3_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner