Aproximačné algoritmy  2-INF-221

Predmet priamo nadväzuje na predmet 2-INF-167 (Výpočtová zložitosť a vypočítateľnosť). Detailnejšie rozpracováva oblasť aproximačných algorimov a zahŕňa techniky návrhu aproximačných algoritmov, dôkazové techniky na odhad aproximačného faktora, neaproximovateľnosť a PCP vetu, triedy aproximovateľnosti a ich úplné problémy a aproximovateľnosť konkrétnych problémov.

Predmet sa vyučuje každoročne v zimnom semestri.

Ak máte ( k predmetu ) akékoľvek otázky, prípadne potrebujete konzultácie, neváhajte ma kontaktovať (najlepšie mailom).

Predmet sa vyučoval v rámci štrukturálneho projektu EU "Príprava štúdia matematiky a informatiky na FMFI UK v anglickom jazyku" v angličtine (otázky, konzultácie, skúšky a všetko boli v slovenčine).

  1. Zložitostné triedy aproximačných algoritmov
  2. Techniky návrhu aproximačných algoritmov
    • PTAS pomocou dekompozície (geometrickej, vonkajškoplanárnej)
    • Techniky založené na lineárnom programovaní
      • deterministické zaokrúhľovanie
      • iterované zaokrúhľovanie
      • randomizované zaokrúhľovanie + derandomizácia
      • primárno-duálne metódy
  3. Negatívne výsledky o aproximovateľnosti
    • PCP veta
    • použitie PCP vety pri dôkazoch neexistencie aproximačných algoritmov
    • AP-redukcia
    • APX úplné problémy
  1. Aproximovateľnosť konkrétnych problémov
    • problém obchodného cestujúceho
      • neaproximovateľnosť všeobecného problému
      • Christofidesov algoritmus pre trojuholníkovú nerovnosť
      • Arorov PTAS pre metrickú verziu
    • toky a rezy
      • max-flow a min-cut ako duálne lineárne programy
      • max-multicomodity-flow a min-multicut
      • min-multiway cut
      • min-k-cut a Gomory-Hu stromy
      • semidefinitné programovanie a max-cut
    • stromy a kostry
      • min-steiner-tree: všeobecná verzia a trojuholníková nerovnosť
      • min-steiner-forest
Väčšina preberanej látky sa dá nájsť v knihe
Na lepšie pochopenie techník založených na lineárnom programovaní odporúčam
Výsledky o neaproximovateľnosti, ktoré nie sú u Vaziraniho (a taktiež pre záujemcov dôkaz PCP vety), sa dajú nájsť tu:
Pre záujemcov o elipsoidovú metódu: časť je u Matouška a Gärtnera; všetky krvavé detaily sú vo výbornej knihe

K dispozícii je stará pracovná verzia poznámok, kde sa dajú nájsť hlavne časti o neaproximovateľnosti. Je v nich dosť preklepov. Plán je čím skôr ich nahradiť novým textom.

Poznámky o variáciách minimálneho rezu a Gomory-Hu stromoch.

Sú tu aj tri časti pripravovaného textu o technikách založených na matematickej optimalizácii:

  1. Pár slov o lineárnom programovaní (update 29.10.2014: preklepy báza vs. nebáza v simplexovom algoritme)
  2. Zaokrúhľovanie lineárnych programov
  3. Dualita v lineárnom programovaní (update 3.2.2014: bugfix v obrázku o Edmondsovom algoritme)

Update 7.1.2017: Kolega A.G. mi písal "su nejakym sposobom pristupne slajdy z predmetu? velmi by to pomohlo". Dovolil by som si nesúhlasiť. Slidy nie sú myslené ako učebné texty. Sú copy-pastovaná podmnožina poznámok vyššie, akurát bez sprievodného textu. Osobne by som odporúčal prečítať textovú verziu, aby nevznikali zbytočné dezinterpretácie, keďže slidy sú myslené na to, že sa k nim na prednáške rozpráva. Ale aby dotyčný kolega nefrflal, že som niečo zatajil , slidy sú tu:

Podmienky skúšky budú upresnené na začiatku semestra. Skúška pozostáva z troch častí: (open book) písomka, na ktorej treba vyriešiť príklady, ústna časť (closed book; písmenká C,D,E sa dajú získať aj iba na základe písomky bez ústnej skúšky) a projekt (bude upresnený, ale v princípe treba naprogramovať niektorý z pokročilých algoritmov z prednášky, najčastejšie Edmondsov algoritmus)

čo?
Implementovať algoritmus na hľadanie minimálneho 1-faktora z prednášky. Na prednáške sme pre jednoduchosť predpokladali, že graf je kompletný graf s párnym počtom vrcholov; v skutočnosti nie je problém bežať algoritmus na ľubovoľnom grafe s tým, že treba domyslieť, kedy zastane, ak daný graf žiaden 1-faktor nemá. Očakávam, že naprogramujete túto druhú verziu.
Na splnenie podmienok Váš algoritmus nemusí byť nijak efektívny (musí byť polynomiálny a musí to byť implementácia algoritmu z prednášky ). Dá sa však dosiahnuť zložitosť $O(n(m+\log n))$ a mať v praxi efektívnu implementáciu s touto zložitosťou je stále otvorený problém. Ak bude viac ako jeden účastník, rád zorganizujem preteky o najrýchlejšiu verziu.
prečo?
Som presvedčený, že na pochopenie (hocijakého) algoritmu je najlepšia cesta naprogramovať si ho. Zároveň je to užitočné programátorské cvičenie.
za čo?
Je to nutná podmienka ku skúške, ale inak na hodnotenie nevplýva. Ak si neviete poradiť (a nechcete prísť na konzultáciu), môžte si pozrieť implementácie, ktoré nájdete na nete. Je na Vás, aby ste sa o to najprv pokúsili sami (je to tak lepšie, naozaj).
ako?
Je mi celkom jedno, v akom jazyku programujete, ale má to byť vaša implementácia (nie volanie knižnice). Pošlite mi mailom zdrojový kód (podľa možnosti slušne napísaný a okomentovaný). Na pomoc pri ladení je tu zopár testovacích dát. Formát vstupu je takýto: na prvom riadku je n m, kde n je počet vrcholov a m je počet hrán. Potom nasleduje m riadkov a v každom z nich sú tri prirodzené čísla u v w, kde w je (celočíselná) váha hrany u-v. Výstup má v prvom riadku hodnotu minimálneho 1-faktora a v ďalších riadkoch vymenované príslušné hrany.
Tu si môžete otestovať malé grafy: buď zadajte vstup vľavo, alebo si nechajte vyrobiť a vyrátať náhodný graf vpravo.

11
4 5
2 3

Tu je niekoľko väčších datasetov.

1000.tgz
1000 vrcholov, 10495 hrán, optimálne riešenie 82612
pr1002.tgz
Dataset z TSPLIB. Je to geometrická inštancia, takže je to úplný graf, ktorého váhy sú euklidovské vzdialenosti bodov v rovine. Má 1002 vrcholov (a teda 501501 hrán). Minimálny 1-faktor má váhu 112630.
10000.tgz
10000 vrcholov, 504929 hrán, optimálne riešenie 977128
20000.tgz
20000 vrcholov, 15009221 hrán, optimálne riešenie 136954