<div dir="ltr"><span style="font-family:arial,sans-serif;font-size:13px">Kedves Érdeklődők!</span><div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">
Szeretnénk meghívni a BME Optimalizálási szemináriumára, ahol <i>Balogh János</i> tart előadást<b> Ládapakolás: online és félig online algoritmusok versenyképességi elemzése</b> címmel március 14-én csütörtökön a H306-os teremben 14:15-ös kezdettel. Az absztraktot lentebb olvashatják.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">Minden érdeklődőt szeretettel várunk!</div><div style="font-family:arial,sans-serif;font-size:13px">
<br></div><div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px"><p class="" align="center" style="margin-bottom:0.0001pt;text-align:center"><a name="_GoBack"></a><b>Ládapakolás: online és félig online
algoritmusok versenyképességi elemzése</b> </p>
<p class="" align="center" style="margin-bottom:0.0001pt;text-align:center"><b><i>Balogh
János</i></b><b> </b></p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">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.</p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">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.</p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">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].</p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">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.</p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">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.</p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">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].</p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">[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.</p>
<p class="" style="margin-bottom:0.0001pt;text-align:justify">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.</p>
<p class="" style="margin-bottom:0.0001pt"><i><u>Hivatkozások:</u></i><b></b></p>
<p class="" style="margin-bottom:0.0001pt">[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.</p>
<p class="" style="margin-bottom:0.0001pt">[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.</p>
<p class="" style="margin-bottom:0.0001pt">[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.</p>
<p class="" style="margin-bottom:0.0001pt">[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</p>
<p class="" style="margin-bottom:0.0001pt">[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</p>
<p class="" style="margin-bottom:0.0001pt">[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.</p></div><div style="font-family:arial,sans-serif;font-size:13px"><span style="text-align:justify;font-family:'Trebuchet MS',Verdana,sans-serif"><br></span></div><div style="font-family:arial,sans-serif;font-size:13px">
<span style="text-align:justify;font-family:'Trebuchet MS',Verdana,sans-serif"><br></span></div><div style="font-family:arial,sans-serif;font-size:13px"><span style="text-align:justify;font-family:'Trebuchet MS',Verdana,sans-serif"><br>
</span></div><div style="font-family:arial,sans-serif;font-size:13px"><span style="text-align:justify;font-family:'Trebuchet MS',Verdana,sans-serif">A szemináriumról az aktuális információk megtalálhatók az alábbi linken:</span></div>
<div style="font-family:arial,sans-serif;font-size:13px"><span style="text-align:justify;font-family:'Trebuchet MS',Verdana,sans-serif"><br></span></div><div style="font-family:arial,sans-serif;font-size:13px"><span style="text-align:justify"><font color="#000000" face="Trebuchet MS, Verdana, sans-serif"><a href="http://www.math.bme.hu/~diffe/szeminarium/opt.shtml#m" target="_blank">http://www.math.bme.hu/~diffe/szeminarium/opt.shtml#m</a></font></span></div>
<div style="font-family:arial,sans-serif;font-size:13px"><span style="text-align:justify;font-family:'Trebuchet MS',Verdana,sans-serif"><br></span></div><div style="font-family:arial,sans-serif;font-size:13px"><span style="text-align:justify;font-family:'Trebuchet MS',Verdana,sans-serif">Üdv.: Zsuzsi</span></div>
</div>