Základní informace

Cvičení je určeno pro přednášku prof. Sgalla.

Ideálním kontaktem na mě je email 1@2354knopkammffczcuni.

Pravidla udělení zápočtu

Za polovinu bodů z domácích úkolů. Pokud nenavštěvujete cvičení, pak ještě dvě třetiny z náhradních úkolů.

Co bylo na cvičeních

09.03. - Set Cover problém, LP, primárné duální programy (S-W: sekce 1.2 - 1.5)
  1. Vertex Cover je speciální případ Set Cover problému
  2. primární program a konstrukce aproximačního algoritmu s faktorem $$f := \max_{e\in E}|\{S\in\mathcal{S}\colon S\in e\}|$$
  3. duální program a konstrukce $f$-aproximačního algoritmu
  4. důkaz, že plrimárně-duální algoritmus je $f$-aproximační
  5. na příště: hladový aproximační algoritmus na Set Cover
16.03. - aproximační schémata ne nepodobná batohu
  1. Pro problém minimalizace součtu vážených časů ukončení na jedno stroji jsme si ukázali, že Smithovo pravidlo dává polynomiální algoritmus.
  2. (S-W ) Pro rozvhování s deadliny na jednom stroji jsme si ukázali DP, který běží v čase $O(nW)$ a ukázali jak přeškálovat váhy jobů tak, abychom získlai FPTAS. Kde $W = \sum_{i = 1}^n w_i.$
  3. Upravili jsme FPTAS pro batoh a získali FPTAS pro zobecněný problém dvou loupežníků (mohou zahazovat části lupu).
23.03. - zrychlujeme batoh
  1. Zopakovali jsme si DP (a hlavně jeho odhady) běžně používaný pro batoh a zjistili, že výsledný FPTAS algoritmus běží v čase $O(n^3\cdot 1/\varepsilon).$
  2. (S-W ) Navrhli jsme hladový $2$-aproximační algoritmus pro batoh: Seřadíme si věci dle poměru $w/s$ ($w$ je váha a $s$ je velikost) tak, že $$w_1/s_1\ge w_2/s_2\ge\cdots\ge w_n/s_n,$$ nastavíme $$k := \max_{l} (\sum_{i = 1}^l s_i \le B)$$ a vrátíme lepší z $\sum_{i = 1}^k w_i$ a $\max_{1\le i\le n} w_i.$
  3. (S-W ) Nazávěr použijeme nově získané odhady pro úpravu škálovacího faktoru v DP pro batoh a nahlédneme, že výsledný čas běhu je $O(n^2\cdot 1/\varepsilon).$
30.03. - základy SDP, charakterizace SDP matic
06.04. - zruseno (jarní škola)
13.04. - Aproximace pomocí SDP
  1. opakování Goemans-Williamson algoritmu
  2. $0.878$-aproximace pro Max-2-SAT problém
  3. poznámky Matta De Vose k důkazu G-W
20.04. - návštěva optimalizačního semináře o GO
27.04. - pujčování auta
Problém pujčování auta dostane číslo $K$ (cena koupě auta) a poté postupně informace o tom, zda auto potřebujeme (sekvence bitů $1111110$ vždy ukončená $0$ znamenající, že jsme auto potřebovali šestkrát a poté již nikdy).
  1. rozmysleli jsme si 2 kompetitivní deterministický algoritmus a ukázali jeho optimalitu
  2. konstantní pravděpodobnost nezávislá na $K$ (např. $1/2$) nutně prohraje po prvním kole
  3. pokud v každém kole koupíme auto s pstí $p = 1/K$ získáme lepší než 2 kompetitvní algoritmus (ale ne o moc, neboť prohráváme v K-tém kole)
  4. je tedy třeba, aby se pravděpodobnost vyvíjela v čase - tedy v i-tém kole koupím s pstí $p_i = i/K$
04.05. - Rektorský sportovní den
11.05. - Problém pujčení/koupení v grafech
Problém je zadán grafem $G = (V,E),$ váhovou funkcí $c: E\to \R^+,$ číslem $K,$ zdrojem $s$ a množinou stoků $T.$ Cílem je naleznout cesty $s-T$ $P_1, P_2, \ldots, P_{|T|}$ (ke každému stoku jednu cestu) takové, že cena přenosu je co možná nejmenší. Cena přenosu se spočítá tak, že se rozhodneme které hrany koupíme (za cenu $K\cdot c(e)$) a které pronajmeme (za každou cestu, která jranu $e$ používá pak zaplatíme $c(e)$)
  1. problém je NP-těžky
  2. začali jsme hledat aproximační algoritmus (fáze nakupování) pomosí Steinerova stromu