On online labeling with polynomially many labels
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%3A00382019" target="_blank" >RIV/67985840:_____/12:00382019 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-33090-2_12" target="_blank" >http://dx.doi.org/10.1007/978-3-642-33090-2_12</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-33090-2_12" target="_blank" >10.1007/978-3-642-33090-2_12</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On online labeling with polynomially many labels
Popis výsledku v původním jazyce
In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,,m} so that the order of labels (strictly) respects theordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.
Název v anglickém jazyce
On online labeling with polynomially many labels
Popis výsledku anglicky
In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,,m} so that the order of labels (strictly) respects theordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>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
Algorithms ? ESA 2012 : 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings
ISBN
978-3-642-33089-6
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
121-132
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Ljubljana
Datum konání akce
10. 9. 2012
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—