On online labeling with polynomially many labels
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On online labeling with polynomially many labels
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Algorithms ? ESA 2012 : 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings
ISBN
978-3-642-33089-6
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
121-132
Publisher name
Springer
Place of publication
Berlin
Event location
Ljubljana
Event date
Sep 10, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—