Number of the records: 1
A lower bound on deterministic online algorithms for scheduling on related machines without preemption
- 1.
SYSNO ASEP 0386905 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title A 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 Title Approximation and Online Algorithms. - Heidelberg : Springer, 2012 / Solis-Oba R. ; Persiano G. - ISBN 978-3-642-29115-9 Pages s. 102-108 Number of pages 7 s. Publication form Print - P Action 9th International Workshop, WAOA 2011 Event date 08.09.2011-09.09.2011 VEvent location Saarbrücken Country DE - Germany Event type WRD Language eng - English Country DE - Germany Keywords algorithm analysis ; problem complexity ; computer science Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10190503 - MU-W (2005-2011) EID SCOPUS 84859345015 DOI 10.1007/978-3-642-29116-6_9 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2013
Number of the records: 1