Tight lower bounds for the online labeling problem

Jan Bulánek, Michal Koucḱ, Michael Saks

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

11 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages1185-1198
Number of pages14
DOIs
StatePublished - 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
Country/TerritoryUnited States
CityNew York, NY
Period5/19/125/22/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • file maintenance problem
  • lower bounds
  • online labeling

Fingerprint

Dive into the research topics of 'Tight lower bounds for the online labeling problem'. Together they form a unique fingerprint.

Cite this