On randomized online labeling with polynomially many labels

Jan Bulánek, Michal Koucký, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


We prove an optimal lower bound on the complexity of randomized algorithms for the online labeling problem with polynomially many labels. All previous work on this problem (both upper and lower bounds) only applied to deterministic algorithms, so this is the first paper addressing the (im)possibility of faster randomized algorithms. Our lower bound Ω(n log(n)) matches the complexity of a known deterministic algorithm for this setting of parameters so it is asymptotically optimal. In the online labeling problem with parameters n and m we are presented with a sequence of n items from a totally ordered universe U and must assign each arriving item a label from the label set {1,2,...,m} so that the order of labels (strictly) respects the ordering on U. As new items arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Number of pages12
EditionPART 1
StatePublished - 2013
Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
Duration: Jul 8 2013Jul 12 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On randomized online labeling with polynomially many labels'. Together they form a unique fingerprint.

Cite this