Počet záznamů: 1  

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

  1. 1.
    0386905 - MÚ 2013 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
    Ebenlendr, Tomáš - Sgall, J.
    A lower bound on deterministic online algorithms for scheduling on related machines without preemption.
    Approximation and Online Algorithms. Heidelberg: Springer, 2012 - (Solis-Oba, R.; Persiano, G.), s. 102-108. Lecture Notes in Computer Science, 7164. ISBN 978-3-642-29115-9.
    [9th International Workshop, WAOA 2011. Saarbrücken (DE), 08.09.2011-09.09.2011]
    Grant CEP: GA AV ČR IAA100190902; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: algorithm analysis * problem complexity * computer science
    Kód oboru RIV: BA - Obecná matematika
    http://link.springer.com/chapter/10.1007%2F978-3-642-29116-6_9

    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.
    Trvalý link: http://hdl.handle.net/11104/0219394
    Název souboruStaženoVelikostKomentářVerzePřístup
    Ebenlendr.pdf2168.5 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1