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

Co se jinam nevejde

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

Příspěvekod mathemage » 10. 6. 2014 18: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í \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!
mathemage
Matfyz(ák|ačka) level III
 
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Login do SIS: had

Zpět na Ostatní

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron