Počet záznamů: 1  

A lower bound on deterministic online algorithms for scheduling on related machines without preemption

  1. 1.
    SYSNO ASEP0386905
    Druh ASEPC - Konferenční příspěvek (mezinárodní konf.)
    Zařazení RIVD - Článek ve sborníku
    NázevA 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 strans. 102-108
    Poč.str.7 s.
    Forma vydáníTištěná - P
    Akce9th International Workshop, WAOA 2011
    Datum konání08.09.2011-09.09.2011
    Místo konáníSaarbrücken
    ZeměDE - Německo
    Typ akceWRD
    Jazyk dok.eng - angličtina
    Země vyd.DE - Německo
    Klíč. slovaalgorithm analysis ; problem complexity ; computer science
    Vědní obor RIVBA - Obecná matematika
    CEPIAA100190902 GA AV ČR - Akademie věd
    1M0545 GA MŠk - Ministerstvo školství, mládeže a tělovýchovy
    CEZAV0Z10190503 - MU-W (2005-2011)
    EID SCOPUS84859345015
    DOI10.1007/978-3-642-29116-6_9
    AnotaceWe 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
    KontaktJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Rok sběru2013
Počet záznamů: 1