Stránka 1 z 1

Toky, řezy, cesty Kolman 9. 6. 2014

Napsal: 10. 6. 2014 19:10
od mathemage
  • 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í \Rightarrow 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 \alpha; tudíž cena řezu z této aproximace je shora odhadnuta \alpha-násobkem objemů vnitřků koulí. Ten je zase shora odhadnut \alpha-násobkem hodnoty zlomkového řešení, z toho příslušný aproximační faktor
    ]
  • Generování sloupců
5,5 dne učení, za 1!