Újszerű párosítás feladatok

Témavezető: Madarasi Péter
ELTE TTK, Operációkutatási Tsz.
email: madarasip@staff.elte.hu

Projekt leírás

Adott egy G=(S,T;E) páros gráf S={s1,...,sn}, T={t1,...,tk} csúcsosztályokkal, egy súlyfüggvény az éleken és egy d pozitív egész. A distance matching feladatban olyan legsúlyosabb M élrészhalmazt keresünk, amelyre a) minden S-beli csúcs foka legfeljebb egy és b) ha sit, sjt benne van M-ben, akkor |j-i| ≥ d.

A kérdés egy alkalmazását kapjuk, amennyiben S csúcsait egymást követő egész napos eseményeknek, T csúcsait biztonsági őröknek feleltetjük meg. Egy s nap és egy t őr között él megy, ha t beosztható az s napra. A feladat minél több naphoz hozzárendelni egy-egy őrt, ügyelve arra, hogy valamennyi őr minden egymást követő d napon legfeljebb egyszer dolgozhat (másképp: minden munkanap után d-1 pihenőnapot kell tartani). A súlyozott esetben az st él súlya az s esemény biztonságát jelöli a t őr felügyelete mellett, és legnagyobb összbiztonságú beosztást keresünk.

Többek között ismertek nehézségi és inapproximálhatósági eredmények, egy hatékony algoritmus nem túl nagy d esetére, és approximációs algoritmusok [1,2].

A feladat kapcsán sok nyitott kérdés van, és több vizsgálható rokon feladat is természetesen adódik. A hallgató feladata az eddigi eredmények feldolgozása, és a kérdéskör további vizsgálata.

Előfeltételek

A munkához szükséges

Hivatkozások

  1. Madarasi P. "The Distance Matching Problem". In: Baïou M., Gendron B., Günlük O., Mahjoub A.R. (eds) Combinatorial Optimization. ISCO 2020. Lecture Notes in Computer Science, vol 12176. Springer, Cham. (2020) https://doi.org/10.1007/978-3-030-53262-8_17
  2. Madarasi, P. "Matchings under distance constraints I.". Annals of Operations Research (2021). https://doi.org/10.1007/s10479-021-04127-8

Korábbi hallgatók