Online algorithms for variants of bin packing

• Název práce v češtině: Online algoritmy pro varianty bin packingu
• Název v anglickém jazyce: Online algorithms for variants of bin packing
• Klíčová slova: online algoritmy, bin packing, analýza nejhoršího případu, barevný bin packing, černobílý bin packing
• Klíčová slova anglicky: online algorithms, bin packing, worst-case analysis, colored bin packing, black and white bin packing
• Akademický rok vypsání: 2013/2014
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. RNDr. Jiří Sgall, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 04.12.2013
• Datum zadání: 04.12.2013
• Datum potvrzení stud. oddělením: 20.02.2014
• Datum a čas obhajoby: 09.09.2014 10:00
• Datum odevzdání elektronické podoby: 30.07.2014
• Datum odevzdání tištěné podoby: 31.07.2014
• Datum proběhlé obhajoby: 09.09.2014
• Oponenti: Mgr. Marek Krčál, Ph.D.

Zásady pro vypracování

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.

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.

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)