Original title:
A Lower Bound for Restricted Randomized On-line Algorithms for Scheduling
Translated title:
Dolní odhad pro omezené pravděpodobnostní online algoritmy pro rozvrhování
Authors:
Tichý, Tomáš Document type: Papers Conference/Event: Week for Doctoral Studentďs 2002, Praha (CZ), 2002-06-11 / 2002-06-14
Year:
2002
Language:
eng Abstract:
[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í.
Keywords:
online; randomized; scheduling Project no.: CEZ:AV0Z1019905 (CEP), LN00A056 (CEP), GA201/01/1195 (CEP), ME 476 Funding provider: GA MŠk, GA ČR, GA MŠk Host item entry: Proceedings of the Week for Doctoral Studentďs 2002
Institution: Institute of Mathematics AS ČR
(web)
Document availability information: Fulltext is available at the institute of the Academy of Sciences. Original record: http://hdl.handle.net/11104/0013991