TY - GEN

T1 - On randomized online labeling with polynomially many labels

AU - Bulánek, Jan

AU - Koucký, Michal

AU - Saks, Michael

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84880251631&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880251631&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_25

DO - 10.1007/978-3-642-39206-1_25

M3 - Conference contribution

AN - SCOPUS:84880251631

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 291

EP - 302

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -