Název: A Lower Bound for Restricted Randomized On-line Algorithms for Scheduling
Překlad názvu: Dolní odhad pro omezené pravděpodobnostní online algoritmy pro rozvrhování
Autoři: Tichý, Tomáš
Typ dokumentu: Příspěvky z konference
Konference/Akce: Week for Doctoral Studentďs 2002, Praha (CZ), 2002-06-11 / 2002-06-14
Rok: 2002
Jazyk: eng
Abstrakt: [eng] [cze]
This paper studies a restricted class of randomized on-line non-preemptive algorithms for scheduling in multiprocessor systems. In this class each task is specified by its processing time and scheduled to a processor with the smallest or $h$th biggest load for a fixed $h$. The competitive ratio is the maximum of the ratios of the expected makespan and the optimal makespan over all. Článek dokazuje dolní odhad pro omezené prqvděpodobnostní online algoritmy pro rozvrhování.
Klíčová slova: online; randomized; scheduling
Číslo projektu: CEZ:AV0Z1019905 (CEP), LN00A056 (CEP), GA201/01/1195 (CEP), ME 476
Poskytovatel projektu: GA MŠk, GA ČR, GA MŠk
Zdrojový dokument: Proceedings of the Week for Doctoral Studentďs 2002

Instituce: Matematický ústav AV ČR (web)
Informace o dostupnosti dokumentu: Dokument je dostupný v příslušném ústavu Akademie věd ČR.
Původní záznam: http://hdl.handle.net/11104/0013991

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-20178


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Matematický ústav
Konferenční materiály > Příspěvky z konference