Optimization and Approximation CSP - NMMB536
|
|
|
||
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
|
|
||
Last update: RNDr. Alexandr Kazda, Ph.D. (23.02.2018)
Zápočet i zkouška se udělují za aktivní účast a řešení problémů během semestru. Charakter zápočtu (průběžná práce) neumožňuje opakování pokusu o získání zápočtu. |
|
||
Last update: T_KA (30.04.2015)
S. Živný. The Complexity of Valued Constraint Satisfaction Problem. Springer, 2012. |
|
||
Last update: RNDr. Alexandr Kazda, Ph.D. (23.02.2018)
Zkouška se uděluje za průběžné řešení problémů během semestru. |
|
||
Last update: T_KA (30.04.2015)
1. Optimalizace a aproximace CSP, vCSP 2.Příklady výpočetních problémů, které lze popsat v jazyku vCSP 3.Lineární relaxace vCSP, použití 4.NP-těžká vCSP 5.Algebraická teorie vCSP - Galoisova korespondence mezi váženými relaxačními a algebraickými klony 6.Aproximační algoritmy založené na lineárním a semidefinitním programování 7.Neaproximovatelná CSP - PCP věta, UGC (Unique Games Conjecture) 8.Řešení problémů s extrémně velkým vstupem
|