Intézeti Szeminárium

Az MTA doktori értekezésem az elmúlt 15 évben elért kutatási eredményekből tartalmaz egy válogatást, amelyeknek a jelentős része az utóbbi 5 évből származik. A fő kutatási területem kombinatorikus optimalizálási algoritmusok, módszerek tervezése, fejlesztése, illetve ezek elemzése elméleti és tapasztalati módszerekkel. A kombinatorikus optimalizálás a diszkrét és alkalmazott matematika egyik fontos területe, amely szorosan kapcsolódik a számítástudományhoz is. A diszkrét optimalizálási modelleket sikeresen alkalmazták olyan területeken, mint a gazdaság, környezettudományok, közlekedés, ipari termelés, stb. Kutatásaim során általában közvetlenül, vagy közvetett módon különböző gyakorlati problémákhoz kapcsolódó feladatokat vizsgáltam.

A disszertáció egyik meghatározó része a ládapakolási algoritmusok elemzésével foglalkozó rész. A ládapakolás az egyik klasszikus probléma a kombinatorikus optimalizálás területén.
Az egydimenziós változatnál adott egy n elemű lista, amelynek minden eleméhez egy méret tartozik. A feladat az, hogy az elemeket minimális számú egységnyi kapacitású ládához rendeljük, azzal a megkötéssel, hogy az egyes ládákhoz rendelt elemek összmérete legfeljebb 1 lehet. Közismert, hogy a probléma NP-nehéz, ezért sok közelítő algoritmust fejlesztettek ki az elmúlt 40 évben. A közelítő algoritmusok minősége központi kérdés az algoritmuselméletben. Számos módszer létezik az algoritmus jóságának mérésére: kísérleti vizsgálat, legrosszabb-eset, illetve versenyképességi és valószínűségi elemzés. A ládapakolási probléma esetén is szokás vizsgálni az online változatot. Egy online algoritmus egyenként pakolja az elemeket. A aktuális elem érkezésekor semmit sem tud a lista fennmaradó részéről: sem az elemek száma, sem a méretük nem ismert. Nyilvánvaló, hogy az online algoritmusok nem rendelkeznek elegendő információval ahhoz, hogy olyan jó pakolást hozzanak létre, mint egy offline algoritmus, ami a teljes bemenetet ismeri. Az előadásban egy az egydimenziós ládapakolási problémára kifejlesztett algoritmus versenyképességi elemzéséről lesz szó, illetve az idő függvényében speciális változatokkal kapcsolatos eredményekre is kitérek.