Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
| Thesis title in Czech: | Stromová šířka, rozšířené formulace CSP a MSO polytopů a jejich algoritmické aplikace |
|---|---|
| Thesis title in English: | Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications |
| Key words: | Rozšířená formulace, stromová šířka, MSO, CSP, kombinatorická optimalizace |
| English key words: | Extended formulation, treewidth, MSO, CSP, combinatorial optimization |
| Academic year of topic announcement: | 2013/2014 |
| Thesis type: | dissertation |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. Mgr. Petr Kolman, Ph.D. |
| Author: | Mgr. Martin Koutecký, Ph.D. - assigned and confirmed by the Study Dept. |
| Date of registration: | 27.09.2013 |
| Date of assignment: | 27.09.2013 |
| Confirmed by Study dept. on: | 22.01.2014 |
| Date and time of defence: | 12.09.2017 16:00 |
| Date of electronic submission: | 28.06.2017 |
| Date of submission of printed version: | 28.06.2017 |
| Date of proceeded defence: | 12.09.2017 |
| Opponents: | Michael R. Fellows |
| Till Tantau | |
| Guidelines |
| Ú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). |
| References |
| 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 |