Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Tight lower bounds for the online labeling problem

Identifikátory výsledku

  • 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>

Alternativní jazyky

  • 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.

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

    BA - Obecná matematika

  • OECD FORD obor

Návaznosti výsledku

  • 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

Ostatní

  • 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ů

Údaje specifické pro druh výsledku

  • 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