Intézeti Szeminárium

Az online ládapakolási feladat egy jól ismert, több mint fél évszázada kutatott területe a számítástudománynak és a kombinatorikus optimalizálásnak. A legrosszabb eset vizsgálatokat tekintve ennek bevett módszere az algoritmusok aszimptotikus versenyképességi hányadosainak vizsgálata. Az erre megadott alsó korlátok pedig behatárolják, hogy egy változat bármely algoritmusa milyen jó lehet, milyen teljesítményt érhet el egyáltalán, illetve ötleteket is szolgáltathat jó algoritmusok megtervezéséhez.
Az elmúlt években az online feladat több változatára sikerült új, javított alsó korlátokat megadni egy előtte a szakirodalomban ezen a területen kevéssé alkalmazott "adaptív" módszer segítségével. Pontosabban ennek egy általánosítását bevezetve és alkalmazva, ami az ún. multiplikatív adaptív konstrukció.

Az online feladatváltozatok közül, ahol ezt felhasználva javítást értünk el, azok közül a legfontosabb és legismertebb talán a klasszikus online ládapakolási feladat. (Megjegyezzük, hogy itt az alsó korláton összesen két alkalommal történt javítás az elmúlt harminc év során.)
Ugyanakkor jelentős mértékű javítást értünk el az elemszám-korlátos illetve a vektorpakolási feladat alsó korlátjain. Az elemszámkorlátos esetben a korlát éles, azaz tovább nem javítható, ha k tart a végtelenbe, ennek értéke 2, míg ennek korábbi ismert értéke 1,55 alatt volt évtizedekig ez előtt. Az online vektorpakolási feladat esetén minden rögzített d dimenziószámra 2,05 alatti érték volt a legjobb ismert alsó korlát. Ezt minden 2-nél nagyobb dimenziószámra javítottuk, nagyobb d dimenziószám esetén d-1 négyzetgyökére.

Valamennyi javított érték jelenleg a szakirodalom legjobb eredménye (aszimptotikus alsó korlátja) az adott változatokon.
Az előadás erről az újonnan megadott technikáról és alkalmazásáról fog szólni.