A lower bound on deterministic online algorithms for scheduling on related machines without preemption
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%3A00386905" target="_blank" >RIV/67985840:_____/12:00386905 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-29116-6_9" target="_blank" >http://dx.doi.org/10.1007/978-3-642-29116-6_9</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-29116-6_9" target="_blank" >10.1007/978-3-642-29116-6_9</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A lower bound on deterministic online algorithms for scheduling on related machines without preemption
Popis výsledku v původním jazyce
We prove a new lower bound of 2.564 on deterministic online algorithms for makespan scheduling on related machines (without preemptions). Previous lower bound was 2.438 by Berman et al. We use an analytical bound on maximal frequency of scheduling jobs instead of the combinatorial bound obtained by computer based search through the graph of possible states of an algorithm in the previous work.
Název v anglickém jazyce
A lower bound on deterministic online algorithms for scheduling on related machines without preemption
Popis výsledku anglicky
We prove a new lower bound of 2.564 on deterministic online algorithms for makespan scheduling on related machines (without preemptions). Previous lower bound was 2.438 by Berman et al. We use an analytical bound on maximal frequency of scheduling jobs instead of the combinatorial bound obtained by computer based search through the graph of possible states of an algorithm in the previous work.
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>Z - Vyzkumny zamer (s odkazem do CEZ)
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
Approximation and online algorithms
ISBN
978-3-642-29115-9
ISSN
—
e-ISSN
—
Počet stran výsledku
7
Strana od-do
102-108
Název nakladatele
Springer
Místo vydání
Heidelberg
Místo konání akce
Saarbrücken
Datum konání akce
8. 9. 2011
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—