Meghívó                             

          Szeretettel várunk minden kedves érdeklődőt a BME

                      Optimalizálás Szemináriumán!

Molnár-Szipai Richárd (BME)
Polinomiális pivot algoritmusok maximális folyam feladaton

Absztrakt:
A maximális folyam feladatra speciális struktúrával rendelkező lineáris programozási feladatként is tekinthetünk. A pivotalgoritmusok fontosabb fogalmainak (bázis, primál és duál megengedettség, stb) szemléletes megfelelőjét már Dantzig is leírta lineáris programozásról szóló könyvében. Ezen felül a gyakorlatban is a hálózati szimplexet tartják az egyik leghatékonyabb eljárásnak.

Ennek ellenére az első bizonyítottan polinomiális változatokat csak 1984-ben (duál szimplex, Orlin), illetve 1990-ben (primál szimplex, Goldfarb és Hao) publikálták. Az előadásban a primál szimplexhez használt technika ismertetése után röviden bemutatjuk az MBU pivot algoritmus különböző változatainak (fízibilitási, primál, duál) polinomialitását, illetve Hochbaum egy kombinatorikus algoritmusát, ami szintén tekinthető egy se nem tisztán primál, se nem duál pivot algoritmusként.