témavezető: Balogh János
helyszín (magyar oldal): SZTE helyszín rövidítés: SZTE
A kutatási téma leírása:
A ládapakolás az egyik klasszikus feladata a számítástudománynak és a kombinatorikus optimalizálásának. Mivel a klasszikus probléma NP-nehéz, és ez legtöbb változatára is elmondható, ezért számos approximációs algoritmust vizsgáltak rá a kutatások. Ennek egyik rokon feladata (néha duálisnak is nevezett) feladata a ládafedési feladat. Az algoritmusok minőségének jellemzésére a leggyakrabban használt módszer az aszimptotikus versenyképességi hányados vizsgálata, de más hányadosok is léteznek az irodalomban. Az utóbbi időben számos egydimenziós és többdimenziós variáns került az érdeklődés homlokterébe. Ezek némelyikén jól működnek a klasszikus algoritmusok variánsai, de van ahol nem.
Az online esetben az input részenként érkezik, és úgy kell döntést hozni, hogy az input további részéről semmilyen információ nem ismert. Az online ládapakolási algoritmusok központi szerepet játszanak az online algoritmusok között. A félig online esetekben valamilyen operáció (pl. átpakolás) megengedett pluszban az online esethez képest, vagy valamilyen információ (pl. méret szerinti teljes rendezettség) ismert az inputról.
A feladat egyes célul kitűzött variánsok, feladatosztályok vizsgálata, a szakirodalom megismerése, algoritmusok tervezése, alsó és felső korlátok megadása algoritmusaik versenyképességére.
felvehető hallgatók száma: 1
Jelentkezési határidő: 2024-09-15
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Bejelentkezés
