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ů.