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

Permalink: http://www.nusl.cz/ntk/nusl-20178


The record appears in these collections:
Research > Institutes ASCR > Institute of Mathematics
Conference materials > Papers