Thesis supervisor: János Balogh
Location of studies (in Hungarian): SZTE Abbreviation of location of studies: SZTE
Description of the research topic:
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.
Login
