Tight lower bounds for the online labeling problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F12%3A00386313" target="_blank" >RIV/67985840:_____/12:00386313 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1145/2213977.2214083" target="_blank" >http://dx.doi.org/10.1145/2213977.2214083</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/2213977.2214083" target="_blank" >10.1145/2213977.2214083</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Tight lower bounds for the online labeling problem

Popis výsledku v původním jazyce

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 storedin 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 toshift 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. Inthis paper we prove lower bounds Omega(log^2 n), for m=Cn, C>1, and Omega(log^3 n), for m=n, that show that known algorithms for this problem are optimal, up to constant factors.

Název v anglickém jazyce

Tight lower bounds for the online labeling problem

Popis výsledku anglicky

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 storedin 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 toshift 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. Inthis paper we prove lower bounds Omega(log^2 n), for m=Cn, C>1, and Omega(log^3 n), for m=n, that show that known algorithms for this problem are optimal, up to constant factors.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F10%2F0854" target="_blank" >GAP202/10/0854: Obvodová složitost a samo-převeditelnost</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 44th symposium on Theory of Computing, STOC'2012

ISBN

978-1-4503-1245-5

ISSN

—

e-ISSN

—

Počet stran výsledku

14

Strana od-do

1185-1198

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

New York

Datum konání akce

19. 5. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—