Tight lower bounds for online labeling problem

Details Tight lower bounds for online labeling problem Tight lower bounds for online labeling problem

2011-12-23

arxiv.org/abs/1112.5636v1

Computer Science

Data Structures and Algorithms

24 pages, 1 figure

Scientific paper

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 done by the algorithm. This problem is non-trivial when n=1, algorithms for this problem with cost O(log(n)^2) per item have been given [IKR81, Wil92, BCD+02]. When m=n, algorithms with cost O(log(n)^3) per item were given [Zha93, BS07]. 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 \Omega(log(n)^2) for the restricted class of smooth algorithms [DSZ05a, Zha93]. 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.

Affiliated with

Also associated with

No associations

Rating

Tight lower bounds for online labeling problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight lower bounds for online labeling problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight lower bounds for online labeling problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-193123