Meghívó
Szeretettel várunk minden kedves érdeklődőt a BME
Optimalizálás Szemináriumán!
Az előadás részletei:
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.
Üdvözlettel,
Majoros Csilla