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

Co se jinam nevejde
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

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

Příspěvek 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!
Carpe Diem!
Odpovědět

Zpět na „Ostatní“