Název: Online algoritmy pro varianty bin packingu
Překlad názvu: Online algorithms for variants of bin packing
Autoři: Veselý, Pavel ; Sgall, Jiří (vedoucí práce) ; Krčál, Marek (oponent)
Typ dokumentu: Diplomové práce
Rok: 2014
Jazyk: eng
Abstrakt: [eng] [cze]
An online algorithm must make decisions immediately and irrevocably based only on a part of the input without any knowledge of the future part of the input. We introduce the competitive analysis of online algorithms, a standard worst-case analysis, and present main results of this analysis on the problem of online Bin Packing and on some of its variants. In Bin Packing, a sequence of items of size up to 1 arrives to be packed into the minimal number of unit capacity bins. Mainly, we focus on Colored Bin Packing in which items have also a color and we cannot pack two items of the same color adjacently in a bin. For Colored Bin Packing, we improve some previous results on the problem with two colors and present the first results for arbitrarily many colors. Most notably, in the important case when all items have size zero, we give an optimal 1.5-competitive algorithm. For items of arbitrary size we present a lower bound of 2.5 and a 3.5-competitive algorithm. Powered by TCPDF (www.tcpdf.org) Online algoritmus se musí rozhodovat okamžitě a nevratně podle části vstupu bez jakékoliv znalosti budoucí části vstupu. Představíme kompetitivní analýzu online algoritmů, což je standardní analýza nejhoršího případu, a hlavní výsledky této analýzy pro problém online bin packingu a pro některé jeho varianty. V bin packingu je úkolem naskládat posloupnost položek o maximální velikosti 1 do minimálního počtu košů jednotkové kapacity. Zaměříme se hlavně na barevný bin packing, v němž mají položky také barvu a je zakázáno mít v koši dvě položky stejné barvy vedle sebe. Vylepšíme některé předchozí výsledky pro problém omezený na dvě barvy a představíme první výsledky pro neomezený počet barev. Hlavním výsledkem je optimální 1.5-kompetitivní algoritmus pro důležitý případ, v němž mají všechny položky velikost 0. Pro položky jakékoliv velikosti dokážeme dolní odhad 2.5 a vytvoříme 3.5-kompetitivní algoritmus. Powered by TCPDF (www.tcpdf.org)
Klíčová slova: analýza nejhoršího případu; barevný bin packing; bin packing; online algoritmy; černobílý bin packing; bin packing; black and white bin packing; colored bin packing; online algorithms; worst-case analysis

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/72132

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-341254


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce