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%2F00216208%3A11320%2F15%3A10316299" target="_blank" >RIV/00216208:11320/15:10316299 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1137/130907653" target="_blank" >http://dx.doi.org/10.1137/130907653</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/130907653" target="_blank" >10.1137/130907653</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 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 haveto 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 moves the algorithm has to do. Thisproblem is nontrivial for n < = m < r. In the case that m = Cn for some C > 1, algorithms are known that solve the problem with cost O(n log(2)(n)) (independent of r). For the case m = n, algorithms with cost O(n log(3)(n)) were given. In

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 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 haveto 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 moves the algorithm has to do. Thisproblem is nontrivial for n < = m < r. In the case that m = Cn for some C > 1, algorithms are known that solve the problem with cost O(n log(2)(n)) (independent of r). For the case m = n, algorithms with cost O(n log(3)(n)) were given. In

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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 periodika

SIAM Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

44

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

33

Strana od-do

1765-1797

Kód UT WoS článku

000367020300008

EID výsledku v databázi Scopus

—