Aproximační algoritmy pro rozvrhování
Thesis title in Czech: | Aproximační algoritmy pro rozvrhování |
---|---|
Thesis title in English: | Approximation algorithms for scheduling |
Academic year of topic announcement: | 2006/2007 |
Thesis type: | diploma thesis |
Thesis language: | |
Department: | Department of Applied Mathematics (32-KAM) |
Supervisor: | prof. RNDr. Jiří Sgall, DrSc. |
Author: | hidden![]() |
Date of registration: | 13.12.2006 |
Date of assignment: | 13.12.2006 |
Guidelines |
Práce se bude zabývat aproximačními algoritmy pro problémy rozvrhování. Zaměří se na dva okruhy problémů.
Prvním okruhem jsou aproximační algoritmy pro tzv. unrelated počítače. Pro tento problém jsou známy 2-aproximační algoritmy. Druhým okruhem je online rozvrhování v reálném čase. V této oblasti je známá řada částečných výsledků, zejména pro jeden počítač. Cílem práce je navrhnout a analyzovat lepší algoritmy pro speciální případy některého z těchto problémů. |
References |
V. V. Vazirani: Approximation Algorithms, Springer, 2001.
A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998. A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998. |