Online algorithms for variants of bin packing
| Thesis title in Czech: | Online algoritmy pro varianty bin packingu |
|---|---|
| Thesis title in English: | Online algorithms for variants of bin packing |
| Key words: | online algoritmy, bin packing, analýza nejhoršího případu, barevný bin packing, černobílý bin packing |
| English key words: | online algorithms, bin packing, worst-case analysis, colored bin packing, black and white bin packing |
| Academic year of topic announcement: | 2013/2014 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. RNDr. Jiří Sgall, DrSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 04.12.2013 |
| Date of assignment: | 04.12.2013 |
| Confirmed by Study dept. on: | 20.02.2014 |
| Date and time of defence: | 09.09.2014 10:00 |
| Date of electronic submission: | 30.07.2014 |
| Date of submission of printed version: | 31.07.2014 |
| Date of proceeded defence: | 09.09.2014 |
| Opponents: | Mgr. Marek Krčál, Ph.D. |
| Guidelines |
| Cílem práce je analyzovat některé varianty problému bin packing.
Jeden ze studovaných problémů bude bin packing omezený podmínkami na barvu prvků, kde je cílem zobecnit předchozí výsledky na případ více barev. Další variantou bude tzv. bin stretching, kde je cílem zlepšit stávající odhady v některých speciálních případech. |
| 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. J. Balogh, J. Békési, G. Dósa, H. Kellerer, Z. Tuza: Black and White Bin Packing. WAOA 2012:131-144. H. Kellerer, V. Kotov: An efficient algorithm for bin stretching. Oper. Res. Lett. (ORL) 41(4):343-346 (2013) |