Toky, řezy, cesty Kolman 9. 6. 2014
Napsal: 10. 6. 2014 19:10
- 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í 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 ; tudíž cena řezu z této aproximace je shora odhadnuta -násobkem objemů vnitřků koulí. Ten je zase shora odhadnut -násobkem hodnoty zlomkového řešení, z toho příslušný aproximační faktor
] - Generování sloupců