Intézeti szeminárium

A Hall tétellel, Dilworth tétellel vagy Menger tételével egy emeleten helyezkedik
el Hakimi régi lemmája irányítatlan gráfok előírt be-fok sorozatú irányíthatóságáról.
Valójában az sem okoz többlet nehézséget, ha a be-fokokra a pontos előírás helyett
csupán alsó-felső korlátok adottak. Lényegesen nehezebb azonban a feladat, ha az
irányítástól azt is elvárjuk, hogy erősen összefüggő, vagy általánosabban, k-él-összefüggő
legyen, de már erre a feladványra is közel 40 esztendeje ismert az irányíthatóság feltétele
éppúgy, mint az irányítást megtaláló hatékony algoritmus. Ugyanakkor a közelmúltig
vajmi keveset tudtunk olyan irányításokról, ahol az irányításnál kiadódó be-fok sorozatnak
egyfajta igazságosságát, kiegyensúlyozottságát, egyenletességét követeljük meg.
Ennek egyik lehetséges formális mércéje (sok más közül) a be-fokok négyzetösszegének
minimuma. Milyen min-max tétel mondható a kérdéses minimumra, hogyan lehet
meghatározni algoritmikusan az ebben az értelemben legigazságosabb irányítást? A
kérdés egy speciális alakja először Harvey, Ladner, Lovász és Tamir egy 2006-os cikkében
bukkant elő, amelyben egy erőforrás hozzárendelési problémát vizsgáltak, elegáns
algoritmust adtak, bár min-max tételt nem.
Egy más jellegű elosztási probléma egy gráf k feszítő fájának megtalálását célozza,
melyek az éleket a legigazságosabban terhelik abban az értelemben, hogy a leginkább
használt él a lehető legkevesebb fában szerepel, ezen belül, a következő leginkább
használt él a legkevesebb fában szerepel, és így tovább. Ha például van a gráfban k
élidegen feszítő fa, azaz minden él terhelése 0 vagy 1, akkor ez garantáltan a
legigazságosabb megoldást jelenti, de persze nem mindig létezik k élidegen feszítő fa.
A jelen előadás célja bepillantást kínálni az igazságos diszkrét optimalizálás területén
Kazuo Murotával az elmúlt két év során közösen elért eredményeinkbe. Kiderül például,
hogy a fenti két egymástól igencsak távolinak tűnő probléma gyökere, és így megoldása
is, egy és ugyanaz.