<div dir="ltr"><div><div><div style="text-align:center"><span style="background-color:rgb(255,255,255)"><font size="4"><b>Meghívó</b></font><br></span></div><span style="background-color:rgb(255,255,255)"><font size="4"><br></font></span><div style="text-align:left"><div style="text-align:center"><span style="background-color:rgb(255,255,255)"><font>Szeretettel várunk minden</font> kedves érdeklődőt a BME<br><span>Optimalizálás</span> <span><span>Szeminárium</span></span>án!</span><span style="background-color:rgb(255,255,255)"></span><br><div style="text-align:left"><span style="background-color:rgb(255,255,255)"></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"></span><br></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"></span></div></div><span style="background-color:rgb(255,255,255)">Az előadás részletei:<br><br></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><i><b>február 25. (csütörtök), 14.15, H306</b></i><br></span></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><br></span></span></div><b>Molnár-Szipai Richárd (BME)<br></b>Polinomiális pivot algoritmusok maximális folyam feladaton
<br>
<br>
<b>Absztrakt</b>:<br>
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.<br><br>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.<br><br><br></div>Üdvözlettel,<br></div>Majoros Csilla<br></div>