Počet záznamů: 1
A lower bound on deterministic online algorithms for scheduling on related machines without preemption
- 1.
SYSNO ASEP 0386905 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A lower bound on deterministic online algorithms for scheduling on related machines without preemption Tvůrce(i) Ebenlendr, Tomáš (MU-W) SAI, RID
Sgall, J. (CZ)Zdroj.dok. Approximation and Online Algorithms. - Heidelberg : Springer, 2012 / Solis-Oba R. ; Persiano G. - ISBN 978-3-642-29115-9 Rozsah stran s. 102-108 Poč.str. 7 s. Forma vydání Tištěná - P Akce 9th International Workshop, WAOA 2011 Datum konání 08.09.2011-09.09.2011 Místo konání Saarbrücken Země DE - Německo Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova algorithm analysis ; problem complexity ; computer science Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) EID SCOPUS 84859345015 DOI 10.1007/978-3-642-29116-6_9 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2013
Počet záznamů: 1