Intézeti szeminárium

Megmutatjuk, hogy az online ládapakolási feladat aszimptotikus alsó
korlátját hogyan lehet némiképp javítani. Valószínű, hogy az első,
nem triviális alsó korlát Yao eredménye 1980-ból, az alsó korlát
értéke 1.5. A korlát úgy adódik, hogy a szerző konstruál egy olyan
tárgy-sorozatot (adversary), amelyet lényegében "nem lehet jól pakolni".
Ezzel egy hosszú, ma is tartó történet kezdődik el. Sokáig van Vliet
megközelítőleg 1.5401-es eredménye tartotta a rekordot, tudomásunk
szerint ez az eredmény kapcsolódik van Vliet 1992-es szegedi
tartózkodásához. Úgy tűnt, ezen az értéken nem is lehet javítani,
mígnem 2012-ben  Balogh, Békési és Galambos publikált egy jobb
eredményt (ennek értéke megközelítőleg 1.5403), amely a korábbi alsó
korlátot eredményező konstrukció meglepő változtatásának eredménye.
Most ezen az eredményen némiképp javítunk, az új korlát 1.54278.
Építünk a korábbi konstrukciók ötleteire, viszont újdonságok is
szükségeltettek a javításhoz, ezek a következők: Egyrészt az alsó
korlát konstrukcióban lehetséges elágazások (branches) vannak, míg a
korábbi konstrukciók lineárisak. Másrészt a konstrukcióban az aktuális
(éppen most pakolt) tárgy méretének "kicsi" vagy "nagy" besorolását
adaptív módon végezzük, ez függ a tárgy pakolásától. Harmadrészt a
bizonyítás egy újfajta, korábban nem alkalmazott technikát használ fel.

Az előadás a következő szerzők közös munkáján alapul: Balogh János,
Békési József, Dósa György, Leah Epstein és Asaf Levin.