December 8-án folytatódik az Online Magyar Operációkutatási Szeminárium

Az előadás kivonata: 

Hogyan lehet egy irányítatlan gráf olyan (erősen összefüggő) irányítását megkeresni, melyre a csúcsok be-fokaiból álló vektor a lehető legegyenletesebb, például abban az értelemben, hogy a be-fokok négyzetösszege minimális? És ha a be-fok vektornak egy input vektortól (valamilyen normában) vett eltérését szeretnénk minimalizálni? Miképp kell egy megadott költség-függvényt a legkisebb mértékben módosítani, hogy egy digráfban kijelölt feszítő fenyő (=arborescence) a legolcsóbb legyen? Hogyan rendeljük az ügyfeleket ügyintézőkhöz, hogy mindenki az ügyének valamelyik szakértőjéhez kerüljön, és a teljes várakozási idő minimális legyen? 

 
A diszkrét optimalizálás alapvető célkitűzése olyan diszkrét struktúrák (gráfok, hálózatok, részbenrendezett halmazok, matroidok) vizsgálata, melyekben létezik hatékony (polinomiális) algoritmus előírt (optimális) objektumok megkeresésére. Korai példa egy maximális súlyú feszító fa megkeresésére szolgáló mohó algoritmus, vagy egy G páros gráf maximális párosítását megtaláló alternáló utas eljárás. Egy ilyen algoritmus kitalálásához gyakran fontos kiinduló pontot jelent egy min-max tétel (pl. Kőnig tétele G maximális párosításának elemszámáról) vagy a keresett objektum létezésére vonatkozó jó karakterizáció (pl. Hall tétele G-beli teljes párosítás létezéséről). Ezek a tételek ugyanis könnyen ellenőrizhető leállási szabályként szolgálnak az algoritmushoz, illetve a kapott eredmény optimalitásának igazolására.

 
Lovász ismerte fel legelőször a diszkrét szubmoduláris függvények és a folytonos konvex függvények között mutatkozó analógiát, majd erre építve Kazuo Murota volt az, aki az elmúlt negyed század során megalapozta a diszkrét konvex analízis (DCA) elméletét. 

 
Jelen célunk annak bemutatása, hogy a területen az elmúlt négy évben Murotával közösen kidolgozott min-max tételek és jó karakterizációk miként használhatók a fentebb konkrétan említett és megannyi további diszkrét optimalizálási feladat megoldására. A megértéshez nincs szükség a DCA fogalmainak vagy eredményeinek ismeretére, csupán a hálózati optimalizálás, matroidelmélet és a poliéderes kombinatorika alapjaira támaszkodunk. 

Az online csatlakozás lehetőségéről a marianna.eisenberg-nagy@uni-corvinus.hu e-mail címen lehet érdeklődni.