Keszthelyi Szilvia: "Mikulás, hipergráfok és matroidok" (Davies, Rothvoss és Zhang cikke)

Alkalmazott Diszkrét Matematika szeminárium

Egy ismert ütemezési feladat a Mikulás problémája. Tegyük fel, hogy a
Mikulás adott ajándékokat szeretne szétosztani gyerekek között úgy, hogy a
legszomorúbb gyerek is a lehető legboldogabb legyen. A feladatra Annamalai
adott 12,33-approximációs algoritmust hipergráfbeli párosításokkal.
Davies, Rothvoss és Zhang bevezette a Mikulás feladat matroidos változatát.
Az algoritmusuk szintén a hipergráf párosításokon alapul, de az
általánosabb feladat megoldásának segítségével a Mikulás problémájára (4 +
eps)-approximációs algoritmust adtak.

For Teams access please contact Zoltán Király (kiraly[at]cs.elte.hu).