A maximális folyam feladatra speciális struktúrával rendelkező lineáris programozási feladatként is tekinthetünk. Apivotalgoritmusok fontosabb fogalmainak (bázis, primál és duálmegengedettsé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 agyakorlatban 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.

Előadó: Molnár-Szipai Richárd (BME)