ARTP - 04 - Balenie do krabíc (bin packing)

Zhrnutie prednášky

Prednáška sa venuje problému balenia do krabíc (bin packing), v ktorom treba predmety s veľkosťami z intervalu (0, 1) naskladať do čo najmenšieho počtu krabíc s kapacitou 1. V online verzii, kde predmety prichádzajú postupne, sa používa heuristika First Fit, ktorá je dvojaproximačná, pretože najviac jedna krabica môže byť zaplnená na menej ako polovicu; v skutočnosti je 1,7-aproximačná. V offline verzii sa predmety najprv zotriedia od najväčšieho po najmenší a potom sa použije First Fit, čo dáva faktor približne 11/9 (zhruba 1,22). Na záver prednáška otvára tému polynomiálnej aproximačnej schémy, ktorá rozdeľuje predmety podľa hranice delta na veľké a malé.

• - Bin packing: naskladať predmety s veľkosťami z (0, 1) do najmenšieho počtu krabíc s kapacitou 1.
• - Online verzia: predmety prichádzajú postupne a o každom sa treba rozhodnúť hneď.
• - First Fit vloží predmet do prvej krabice, kde sa zmestí, inak otvorí novú.
• - Dôkaz dvojaproximácie: najviac jedna krabica je zaplnená pod polovicu, preto M ≤ 2·OPT; dá sa ukázať aj faktor 1,7.
• - Offline verzia: predmety sa zotriedia od najväčšieho po najmenší a použije sa First Fit (faktor 11/9 ≈ 1,22).
• - Cieľom je polynomiálna aproximačná schéma s garanciou (1 + ε)·OPT pre ľubovoľné ε > 0.
• - Idea schémy: hranica delta rozdelí predmety na veľké (náročné na umiestnenie) a malé (ľahko sa dosypú).

Zhrnutie pripravené s pomocou AI z prepisu videa.