[Mat08] Meghívó a BME Optimalizálási Szemináriumára - márc. 14.

[Zsuzsanna Barta]

Kedves Érdeklődők!

Szeretnénk meghívni a BME Optimalizálási szemináriumára, ahol *Balogh
János*tart előadást
* Ládapakolás: online és félig online algoritmusok versenyképességi elemzése
* címmel március 14-én csütörtökön a H306-os teremben 14:15-ös kezdettel.
Az absztraktot lentebb olvashatják.

Minden érdeklődőt szeretettel várunk!


*Ládapakolás: online és félig online algoritmusok versenyképességi elemzése*


*Balogh János** *

A ládapakolás egy jól ismert, klasszikus kombinatorikus optimalizálási
probléma. A ládapakolási algoritmusok legrosszabb eset elemzése általában
az aszimptotikus versenyképességi hányadost vizsgálva történik, bár az
utóbbi időben az abszolút versenyképességi hányadossal történő elemzés is
létjogosultságot nyert.

Az előadás első részében áttekintjük az online ládapakolási algoritmusok
legrosszabb eset elemzésénél használatos módszereket, a legfontosabb
algoritmusok alapelveit, az elemzés néhány technikáját.

Ezután áttekintjük néhány, az online és félig online ládapakolás területén
elért eredményünket [1-6].

A klasszikus online feladatra vonatkozó legjobb alsó korlátot egy húszéves
eredményt megjavítva adtuk meg 2012-ben [1]. (Az aszimptotikus
versenyképességi hányadost vizsgálva itt és az előadás hátralévő részében
is.) Itt javítottunk [1] egy másik, 30 éves eredményt is, bármely,
nem-növekvő elemméretű listákat pakoló online ládapakolási algoritmusra. A
régi alsó korlát 8/7, az új eredmény 54/47.

Néhány további alsó és felső korlátot adtunk meg egy másik, félig online
ládapakolási feladatra [2-4]. Nevezetesen, amikor az algoritmus korlátozott
átpakolást is végezhet, minden egyes lépésben (lépés alatt az input egy új
elemének érkezését értjük) az adott érkező elem elpakolása mellett k darab
korábban elpakolt elemet is átpakolhat (más ládába rakhat át). Itt k egy
előre rögzített pozitív egész.

Vizsgáltuk azt a félig online ládapakolási feladatot vizsgáltuk, amikor az
online algoritmus számára az optimum értéke is megadott előre, az input
részeként. Erre a feladatra egy 1,323-as alsó korlátot adtunk meg [5].

[6]-ban egy új feladatot definiáltunk, a fekete-fehér ládapakolási
feladatot. Ekkor az input lista minden eleméhez egy szín is meg van adva
(fekete vagy fehér színű az adott elem), és van egy további pakolási
szabály is előírva: fekete elemre csak fehér, fehérre pedig csak fekete
rakható (minden ládában alternálnia kell az oda pakolt elemek színének).
Tárgyaljuk az ezen feladat online változatára megadott 1,72-es alsó
korlátot eredményező konstrukció alapötletét. Az 1,72-es alsó korlát
bizonyítja, hogy a fekete-fehér online ládapakolási feladat nehezebb, mint
a klasszikus online ládapakolási feladat, hiszen arra egy (legfeljebb)
1,58889-es aszimptotikus versenyképességi hányadosú algoritmus ismert.

Ez előadás közös munka a hivatkozások társszerzőivel, Békési Józseffel,
Dósa Györggyel, Leah Epsteinnel, Galambos Gáborral, Hans Kellererrel,
Markót Mihály Csabával és Tuza Zsolttal.

*Hivatkozások:***

[1] Balogh, J., J. Békési, and G. Galambos, New Lower Bounds for Certain
Classes of Bin Packing Algorithms, Theoretical Computer Science,
440-441(2012), 1-13.

[2] Balogh, J., J. Békési, G. Galambos, and G. Reinelt, Lower bound for the
online bin packing problem with restricted repacking, SIAM Journal on
Computing, 38(2008), 398-410.

[3] Balogh, J., J. Békési, G. Galambos, and M.Cs. Markót, Improved lower
bounds for semi-on-line bin packing problems, Computing, 84(2009), 139-148.

[4] Balogh, J., J. Békési, G. Galambos, and G. Reinelt, On-line bin packing
with restricted repacking, Journal of Combinatorial Optimization, Online
First, 2012. DOI: 10.1007/s10878-012-9489-4

[5] Balogh, J. and J. Békési, Semi-on-line bin packing: a short overview
and a new lower bound, Central European Journal of Operations Research,
Online First, 2012. DOI: 10.1007/s10100-012-0266-3

[6] Balogh J., J. Békési, Gy. Dósa, H. Kellerer, and Zs. Tuza, Black and
White Bin Packing, In: Thomas Erlebach, Giuseppe Persiano (Eds), WAOA 2012,
Workshop on Approximation and Online Algorithms, Lecture Notes in Computer
Science, 2013, megjelenés előtt.



A szemináriumról az aktuális információk megtalálhatók az alábbi linken:

http://www.math.bme.hu/~diffe/szeminarium/opt.shtml#m

Üdv.: Zsuzsi
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: http://lists.math.bme.hu/pipermail/mat08/attachments/20130311/db928976/attachment.htm