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 -