Pseudo-Booleovská optimalizace

Sylabus

1. Zavedení nutných pojmů a značení, příklady optimalizačních problémů, které lze formulovat jako minimalizaci nebo maximalizaci pseudo-booleovské funkce.

2. Reprezentace pseudo-booleovských funkcí (multilineární polynomy, posiformy) a převody mezi nimi.

3. Zaokrouhlování, derandomizace, lokální optima.

4. Redukce obecné optimalizace na kvadratickou.

5. Maximalizace pro posiformy.

6. Aplikace v teorii her.

7. Kvadratické optimalizace a roof-dualita.

8. Persistence a souvislost s toky v sítích.

9. Zobecnění roof-duality, hierarchie odhadů.

10. Aproximace

11. Speciální třídy.

Anotace

Tato přednáška je vhodná pro všechny studenty magisterského studia a doktorandy, kteří mají alespoň základní znalosti z matematické logiky, teorie grafů, toků v sítích a složitosti algoritmů. Přednáška pokrývá několik oblastí zajímavých problémů soustředěných okolo pseudo-boolovských funkcí, zejména se zaměřením na aplikace pseudo-boolovských funkcí při řešení těžkých optimalizačních problémů.