od mathemage » 10. 6. 2014 19:10
[list]
[*] Přehled toků a jejich duální problémy
[
součtové vs. spravedlivé (souběžné) toky <-> multiřez vs. nejřidší řez
potrubní algoritmus a myšlenka, jež se za ním skrývá:
1) celá síť má stejný objem jako hodnota zlomkového řešení
2) koule jsou disjunktní [latex]\Rightarrow[/latex] součet objemů je shora omezen objemem sítě a tím pádem i hodnotou zlomkového řešení
3) min vzorce/poměru, který používáme při hledání ideálního poloměru, je shora odhadnut jistou hodnotou [latex]\alpha[/latex]; tudíž cena řezu z této aproximace je shora odhadnuta [latex]\alpha[/latex]-násobkem objemů vnitřků koulí. Ten je zase shora odhadnut [latex]\alpha[/latex]-násobkem hodnoty zlomkového řešení, z toho příslušný aproximační faktor
]
[*] Generování sloupců[/list]
5,5 dne učení, za 1!