Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
| Název práce v češtině: | Stromová šířka, rozšířené formulace CSP a MSO polytopů a jejich algoritmické aplikace |
|---|---|
| Název v anglickém jazyce: | Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications |
| Klíčová slova: | Rozšířená formulace, stromová šířka, MSO, CSP, kombinatorická optimalizace |
| Klíčová slova anglicky: | Extended formulation, treewidth, MSO, CSP, combinatorial optimization |
| Akademický rok vypsání: | 2013/2014 |
| Typ práce: | disertační práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. Mgr. Petr Kolman, Ph.D. |
| Řešitel: | Mgr. Martin Koutecký, Ph.D. - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 27.09.2013 |
| Datum zadání: | 27.09.2013 |
| Datum potvrzení stud. oddělením: | 22.01.2014 |
| Datum a čas obhajoby: | 12.09.2017 16:00 |
| Datum odevzdání elektronické podoby: | 28.06.2017 |
| Datum odevzdání tištěné podoby: | 28.06.2017 |
| Datum proběhlé obhajoby: | 12.09.2017 |
| Oponenti: | Michael R. Fellows |
| Till Tantau | |
| Zásady pro vypracování |
| Úkolem studenta bude především zkoumání horních a dolních mezí na aproximovatelnost některých kombinatorických NP-težkých problémů (např. problém minimálního řezu pro toky omezené délky nebo pro vícecestné multikomodintí toky). |
| Seznam odborné literatury |
| The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge University Press 2011
Combinatorial Optimization, Alexander Schrijver, Springer 2003 Approximation Algorithms, Vijay V. Vazirani, Springer 2004 |