TY - GEN
T1 - Tight lower bounds for the online labeling problem
AU - Bulánek, Jan
AU - Koucḱ, Michal
AU - Saks, Michael
PY - 2012
Y1 - 2012
N2 - We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m ≥ n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r ≤ m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves the algorithm has to do. This problem is non-trivial when n ≤ m < r. In the case that m = Cn for some C>1, algorithms for this problem with cost O(log(n) 2) per item have been given [Itai et al. (1981), Willard (1992), Bender et al. (2002)]. When m=n, algorithms with cost O(log(n) 3) per item were given [Zhang (1993),Bird and Sadnicki (2007)]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Ω(log(n) 2) for the restricted class of smooth algorithms [Dietz et al. (2005), Zhang (1993)]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
AB - We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m ≥ n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r ≤ m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves the algorithm has to do. This problem is non-trivial when n ≤ m < r. In the case that m = Cn for some C>1, algorithms for this problem with cost O(log(n) 2) per item have been given [Itai et al. (1981), Willard (1992), Bender et al. (2002)]. When m=n, algorithms with cost O(log(n) 3) per item were given [Zhang (1993),Bird and Sadnicki (2007)]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Ω(log(n) 2) for the restricted class of smooth algorithms [Dietz et al. (2005), Zhang (1993)]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
KW - file maintenance problem
KW - lower bounds
KW - online labeling
UR - http://www.scopus.com/inward/record.url?scp=84862611470&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862611470&partnerID=8YFLogxK
U2 - 10.1145/2213977.2214083
DO - 10.1145/2213977.2214083
M3 - Conference contribution
AN - SCOPUS:84862611470
SN - 9781450312455
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1185
EP - 1198
BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12
Y2 - 19 May 2012 through 22 May 2012
ER -