Jelenlegi hely

Intézeti szeminárium

Félév: 
2018/19 II.félév
Helyszín: 
Árpád tér 2. II. em. 220. sz.
Dátum: 
2019-04-09
Időpont: 
14:00-15:00
Előadó: 
Dósa György (Pannon Egyetem)
Cím: 
Javított alsó korlát az online ládapakolási feladatra
Absztrakt: 

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.