Original title: Online algoritmy pro varianty bin packingu
Translated title: Online algorithms for variants of bin packing
Authors: Veselý, Pavel ; Sgall, Jiří (advisor) ; Krčál, Marek (referee)
Document type: Master’s theses
Year: 2014
Language: eng
Abstract: [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)
Keywords: bin packing; black and white bin packing; colored bin packing; online algorithms; worst-case analysis; analýza nejhoršího případu; barevný bin packing; bin packing; online algoritmy; černobílý bin packing

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/72132

Permalink: http://www.nusl.cz/ntk/nusl-341254


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses