Aproximácia optimalizačných problémov

2-INF-221

Predmet nadväzuje na predmet 1-INF-167 (Výpočtová zložitosť a vypočítateľnosť) a 1-INF-310 (Tvorba efektívnych algoritmov). Zaoberá sa problémami, kde je treba nájsť optimálne (minimálne alebo maximálne) riešenie. Ak sú výpočtovo ťažké, snažíme sa nájsť algoritmus, ktorý vždy vráti riešenie, ktoré síce nie je optimálne, ale vieme zaručiť, že od optimálneho nie je príliš ďaleko. Predmet pokrýva tri okruhy:

  • Techniky návrhu aproximačných algoritmov
    • Zaokrúhľovanie v dynamickom programovaní
    • Dekompozícia priestoru
    • Derandomizácia
    • Techniky založené na lineárnom programovaní
      • vzťah medzi LP a ILP
      • deterministické zaokrúhľovanie
      • randomizované zaokrúhľovanie
      • iteratívne zaokrúhľovanie
      • primárno-duálne techniky
  • Algoritmy pre konkrétne problémy
    • SAT
    • Problém obchodného cestujúceho
    • Toky a rezy v grafoch
    • Najlacnejšie podgrafy
    • MAX-FLOW a semidefinitné programy
  • Zložitostné aspeky
    • Vzťah s triedami P, NP
    • PCP veta
    • Neaproximovateľnosť problémov
    • Redukcia a úplnosť v aproximačných triedach

Materiál

Vijay V. Vazirani: Approximation Algorithms
Väčšina preberanej látky sa dá nájsť tu. Prudko odporúčaná.

David P. Williamson, David B. Shmoys: The Design of Approximation Algorithms
Niektoré algoritmy, ktoré nie sú vo Vaziraniho knihe, sa dajú nájsť tu.

Martin Grötschel, Laszlo Lovasz, Alexander Schrijver: Geometric Algorithms and Combinatorial Optimization
Pre záujemcov o hlbšie pochopenie elipsoidovej metódy, ktorá je na prednáške iba spomenutá.

Giorgio Ausiello a spol.: Complexity and Approximation
Niektoré algoritmy, a takisto časti o zložitosti, idú prevažne podľa tejto knihy.

Jiří Matoušek, Bernd Gärtner: Understanding and Using Linear Programming
Na prednáške sa nestihne hlbšie rozprávať o lineárnom programovaní. Odporúčam prečítať napr. túto knihu, aby ste mali lepší prehľad, čo používame.

Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach
Výborná učebnica výpočtovej zložitosti všeobecne. Odporúčaná pre záujemcov o dôkaz PCP vety a širšie súvislosti.

Okrem kníh sú k dispozícii časti pripravovaného materiálu: Pri časti prednášok používam prezentáciu. Je myslená ako sprievod k prednášaniu a nie je samostatne zrozumiteľná (v podstate sú to obrázky z materiálov vyššie bez sprievodného textu). Arorov článok o PTAS pre metrický TSP je prístupný tu: www.cs.princeton.edu/~arora/pubs/tsp.ps.

Data

Testovacie dáta k implementácii Edmodsovho algoritmu sú tu.