Bejelentkezés
 Fórum
 
 
Témakiírás
 
Egyes ládapakolási és ládafedési algoritmusok vizsgálata

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
informatikai tudományok
Informatika Doktori Iskola

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ő: 2020-05-31

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 2.2358 ( 2017. X. 31. )