Number of the records: 1
Preemptive Online Scheduling: Optimal Algorithms for All Speeds
- 1.
SYSNO ASEP 0334960 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Preemptive Online Scheduling: Optimal Algorithms for All Speeds Title Preemptivní online rozvrhování: optimální algoritmy pro všechny rychlosti Author(s) Ebenlendr, Tomáš (MU-W) SAI, RID
Jawor, W. (US)
Sgall, Jiří (MU-W) RID, ORCID, SAISource Title Algorithmica. - : Springer - ISSN 0178-4617
Roč. 53, č. 4 (2009), s. 504-522Number of pages 19 s. Language eng - English Country US - United States Keywords anline algorithms ; scheduling Subject RIV IN - Informatics, Computer Science R&D Projects 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) GA201/05/0124 GA ČR - Czech Science Foundation (CSF) IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000264698900005 DOI 10.1007/s00453-008-9235-6 Annotation 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.054 and e approximate to 2.718. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2010
Number of the records: 1