Thesis (Selection of subject)Thesis (Selection of subject)(version: 381)
Thesis details
   Login via CAS
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
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html