A stabil hozzárendelés probléma általánosításai
| Témavezető: | Király Tamás |
| ELTE TTK, Operációkutatási Tsz. | |
| email: | tamas.kiraly@ttk.elte.hu |
Projekt leírás
A stabil párosítás feladatban minden csúcsnak van egy (nem feltétlenül teljes) preferencialistája a többi csúcsról. Olyan párosítást keresünk, ami nem tartalmaz blokkoló párt, azaz olyan élet, ami nincs benne a párosításban, és mindkét végpont jobban járna, ha leváltaná a másikra az aktuális párját. A stabil hozzárendelés problémában egy páros gráfunk van, a csúcsok egyik osztálya a kórházak/egyetemek, melyeknek adott egy kapacitása is, a másik az orvosok/diákok. Itt persze a hozzárendelésnél ügyelni kell a kapacitások megtartására is. A feladat a kórház/egyetem csúcsok megtöbbszörözésével könnyen visszavezethető a stabil párosítás keresésre. Az alapesetben ilyen mindig létezik és a Gale-Shapley algoritmus lineáris időben megoldja a problémát. A feladatnak azonban számos általánosítása ismert, amikor már nem feltétlenül fog létezni stabil hozzárendelés, vagy ha létezik is jóval nehezebb megtalálni. Például már azzal az egyszerű módosítással is jócskán bonyolódik a helyzet, ha a jól megszokott kórház-orvos hozzárendelésnél megengedünk az orvosok közt párokat is. A feladat a probléma különböző általánosításainak és az azokra született eddigi algoritmusoknak tanulmányozása lenne, illetve új algoritmusok keresése/javítás az eddigieken.