Preemptivní online rozvrhování: Optimální algoritmy pro všechny rychlosti
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F06%3A00076019" target="_blank" >RIV/67985840:_____/06:00076019 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Preemptive Online Scheduling: Optimal Algorithms for All Speeds
Popis výsledku v původním jazyce
Our main result is an optimal online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize makespan. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. Together with a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between $2.0545$ and $e/approx 2.718$.
Název v anglickém jazyce
Preemptive Online Scheduling: Optimal Algorithms for All Speeds
Popis výsledku anglicky
Our main result is an optimal online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize makespan. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. Together with a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between $2.0545$ and $e/approx 2.718$.
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
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of the 14th European Symposium on Algorithms (ESA)
ISBN
3-540-38875-3
ISSN
—
e-ISSN
—
Počet stran výsledku
13
Strana od-do
327-339
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Zurich
Datum konání akce
11. 9. 2006
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—