Extended formulations of polytopes Tiwary 14. 5. 2014

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:

Extended formulations of polytopes Tiwary 14. 5. 2014

Příspěvek od mathemage »

Hans si sedl před tabuli na chodbě na KAMu a dělal, že je studentem, kterého mám naučit jeho předmět. V angličtině jsem začal u tabule přednášet:
  • polytop, extended formulation, extended comlexity
  • slack matrix, non-negative rank, jejich souvislost
  • protokol, souvislost s rankem
  • aplikace pro spanning tree polytope (tady jsem popleltl s cut-polytope, pak totiz šel řešit NP-úplný max-cut v poly-čase, ale nakonec to přešel)
  • konkrétně protokol pro span. tree polytope
Doplňující otázky (přemýšlecí, co nebylo na přednášce):
  • jak upravit protokol pro čistě 1-směrnou komunikaci
    [Jeden hráč "simuluje" zaslané bity 2. hráče pravděpodobnostně a pošle informaci o simulovaných bitech druhému. Pokud je byl býval nemohl zaslat, vydá nulový výstup, jinak je zakomponuje do výpočtu. - viz příklad dále]
  • 1-směrný protokol pro span. tree polytope.
    [Bob simuluje pravděpodobnostně Alicin výběr kořene u, a pošle ho společně s orientovanou hranou Alice. Pokud ona měla u\in U, započítá do výstupu, jinak vrátí 0. Ke konci se musí upravit pravděpodobnosti, vynásobením vhodného faktoru úměrného velikosti U
  • Bipyramida B (polytop P s horní a spodní špičkou v přidané dimenzi, něco jako 2 homog. kužele nahoru a dolu) -> jeji ext. complexity oproti původnímu polytopu P
    (zespoda aspoň xc(P), protože P je projekce B. Zeshora nejvýše xc(P)+2, důsledek věty o ext. complexity konvexního sjednocení.
I když jsem některé doplň. ot. nevěděl, dostal jsem nakonec za 1, páč je to fakt nová oblast matematiky. :twisted:
Carpe Diem!
Odpovědět

Zpět na „I4 Ostatní Diskrétní modely a algoritmy“