Egerváry Jenő páros gráfok maximális súlyú teljes párosítására vonatkozó min-max tétele és algoritmikus megközelítési módja a kombinatorikus optimalizálás egyik legfontosabb kiindulópontjává vált. Ebből fejlődött ki a Kuhn-féle Magyar módszer, innen ered a költséges hálózati folyam probléma, erre épül az általános gráfok párosításelmélete, valamint a matroidelmélet egyik legfontosabb algoritmusa súlyozott matroidmetszet kiszámítására.

Tíz évvel ezelőtt ünnepeltük a Magyar Tudományos Akadémián a Magyar módszer 50. születésnapját. Az idei kerek évfordulón az MTA-ELTE Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport (EGRES) tagjai ízelítőt adnak az eltelt időszak eredményeiből.

Külön hangsúlyt kap a szub- és szupermoduláris függvények, valamint a paritás mélyreható szerepének bemutatása. A vizsgálatokban központi helyet foglalnak el a gráfok összefüggőségégével és merevségével kapcsolatos különféle kérdések.

Strukturális eredmények kidolgozása éppoly fontos célt jelent, mint hatékony, pontos vagy közelítő algoritmusok megkonstruálása. Kitérünk az elmélet és a valódi alkalmazások kapcsolatára is.

A tudományos ülés elnöke:

Pálfy Péter Pál, az MTA rendes tagja, a Matematikai Tudományok Osztálya elnöke

Az ülés időpontja:

2015. november 11. (szerda) 14 óra

Az ülés helyszíne:

MTA Székház, Felolvasóterem (1051 Budapest, Széchenyi István tér 9., 1. em.)

PrKattintson ide a rendezvényen elhangzó előadások rövid kivonataiért!ogram

Jordán Tibor: Kombinatorikus merevség és alkalmazásai

Pap Gyula: Párosítások, diszjunkt utak és matroidok

Jüttner Alpár: Gyakorlati kombinatorikus optimalizálás

Szünet

Király Tamás: Matroidok, poliéderek és gráfalgoritmusok

Végh László: Egzakt és közelítő algoritmusok összefüggőség-növelési problémákra

Frank András: Gráf-optimalizálási problémák közös gyökere: a szupermoduláris fedési tétel