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

• 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!