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 - assigned and confirmed by the Study Dept. |
| 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. |