Number of the records: 1  

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

  1. 1.
    SYSNO ASEP0386905
    Document TypeC - Proceedings Paper (int. conf.)
    R&D Document TypeConference Paper
    TitleA lower bound on deterministic online algorithms for scheduling on related machines without preemption
    Author(s) Ebenlendr, Tomáš (MU-W) SAI, RID
    Sgall, J. (CZ)
    Source TitleApproximation and Online Algorithms. - Heidelberg : Springer, 2012 / Solis-Oba R. ; Persiano G. - ISBN 978-3-642-29115-9
    Pagess. 102-108
    Number of pages7 s.
    Publication formPrint - P
    Action9th International Workshop, WAOA 2011
    Event date08.09.2011-09.09.2011
    VEvent locationSaarbrücken
    CountryDE - Germany
    Event typeWRD
    Languageeng - English
    CountryDE - Germany
    Keywordsalgorithm analysis ; problem complexity ; computer science
    Subject RIVBA - General Mathematics
    R&D ProjectsIAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
    1M0545 GA MŠk - Ministry of Education, Youth and Sports (MEYS)
    CEZAV0Z10190503 - MU-W (2005-2011)
    EID SCOPUS84859345015
    DOI10.1007/978-3-642-29116-6_9
    AnnotationWe 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.
    WorkplaceMathematical Institute
    ContactJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Year of Publishing2013
Number of the records: 1