|
|
Online Bin Stretching: Algorithms and Computer Lower Bounds
Böhm, Martin ; Sgall, Jiří (vedoucí práce) ; Durr, Christoph (oponent) ; Kellerer, Hans (oponent)
Online Bin Stretching: algoritmy a strojové dolní odhady Autor: Martin Böhm Abstrakt: Zabýváme se problémem v oblasti semi-online algoritmů, který se nazývá Online Bin Stretching. Můžeme tento problém chápat jako pro- blém opětovného pakování předmětů: cílem algoritmu je zapakovat před- měty různých velikostí do m kontejnerů identické kapacity R > 1. Objekty na vstupu přicházejí jeden po druhém a algoritmus musí přiřadit předmět do kontejneru dříve, než se objeví předmět další. Zvláštnost tohoto konkrétního problému je existence zaručené vlastnosti vstupu, kterou algoritmus zná. Algoritmus totiž už od začátku vstupu má zaručeno, že existuje pakování celého vstupu do m kontejnerů kapacity 1. Naším cílem je navrhnout algoritmy, které pakují jeden objekt po dru- hém a kterým se podaří vstup zapakovat do co nejmenší možné kapacity R. V této dizertační práci představíme několik nových výsledků kolem On- line Bin Stretchingu. Zaprvé, navrhneme algoritmus, který napakuje všechny objekty do m kontejnerů s kapacitou 1,5, a to pro libovolnou počáteční hodnotu m. Zadruhé se soustředíme na podproblém, ve kterém je počet kontejnerů nízký a pevný, například 3. Pro tento model představíme algo- ritmus, který zapakuje vstup do 3 binů s kapacitou 1,375. Nakonec navrhneme a naimplementujeme počítačový program, který bude...
|
host ::
RSS.