Aproximační algoritmy pro rozvrhování
| Název práce v češtině: | Aproximační algoritmy pro rozvrhování |
|---|---|
| Název v anglickém jazyce: | Approximation algorithms for scheduling |
| Akademický rok vypsání: | 2006/2007 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | prof. RNDr. Jiří Sgall, DrSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 13.12.2006 |
| Datum zadání: | 13.12.2006 |
| Zásady pro vypracování |
| 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ů. |
| Seznam odborné literatury |
| 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. |