O semi-online pokrývání počítačů

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F06%3A00041413" target="_blank" >RIV/67985840:_____/06:00041413 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
A note on semi-online machine covering
Popis výsledku v původním jazyce
In the machine cover problem we are given $m$ machines and $n$ jobs to be assigned (scheduled) so that the smallest load of a machine is as large as possible. A semi-online algorithms is given in advance the optimal value of the smallest load for the given instance, and then the jobs are scheduled one by one as they arrive, without any knowledge of the following jobs. We present a deterministic algorithm with competitive ratio $11/6/leq 1.834$ for machine covering with any number of machines and a lowerbound showing that no deterministic algorithm can have a competitive ratio below $43/24/geq 1.791$.
Název v anglickém jazyce
A note on semi-online machine covering
Popis výsledku anglicky
In the machine cover problem we are given $m$ machines and $n$ jobs to be assigned (scheduled) so that the smallest load of a machine is as large as possible. A semi-online algorithms is given in advance the optimal value of the smallest load for the given instance, and then the jobs are scheduled one by one as they arrive, without any knowledge of the following jobs. We present a deterministic algorithm with competitive ratio $11/6/leq 1.834$ for machine covering with any number of machines and a lowerbound showing that no deterministic algorithm can have a competitive ratio below $43/24/geq 1.791$.

Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2006
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 3rd Workshop on Approximation and Online Algorithms (WAOA)
ISBN
3-540-32207-8
ISSN
—
e-ISSN
—
Počet stran výsledku
9
Strana od-do
110-118
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Palma de Mallorca
Datum konání akce
6. 10. 2005
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)