Semidefinitní programování - NOPT050

• Anglický název: Semidefinite Programming
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2011 do 2016
• Semestr: zimní
• E-Kredity: 6
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jiří Matoušek, DrSc.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Poslední úprava: T_KAM (18.04.2010)

Pro magisterské studenty i doktorandy. Jednorázová přednáška, nepočítá se s brzkým opakováním. Semidefinitní programování se v posledních zhruba patnácti letech stalo jedním z nejdůležitějších nástrojů na řešení obtížných problémů kombinatorické optimalizace. Probereme matematické a algoritmické základy semidefinitního programování a několik aplikací na aproximační algoritmy.

angličtina

Poslední úprava: T_KAM (18.04.2010)

For Msc. or doctoral students. A one-time lecture, no repetition planned in the next few years. Can be taught in English. Over the last fifteen years, semidefinite programming has become an important tool for approximate solutions of hard combinatorial problems. We cover mathematical and algorithmic foundations of semidefinite programming, and we present several applications in approximation algorithms.

Literatura

čeština

Poslední úprava: T_KAM (18.04.2010)

B. Gartner, J. Matoušek: Approximation Algorithms and Semidefinite Programming, učební text, bude posluchačům k dispozici.

angličtina

Poslední úprava: T_KAM (18.04.2010)

B. Gartner, J. Matoušek: Approximation Algorithms and Semidefinite Programming, lecture notes, will be available to the participants.

Sylabus

čeština

Poslední úprava: T_KAM (18.04.2010)

Kuželové programování, dualita. Přehled algoritmických technik pro semidefinitní programování. Goemansův-Williamsonův algoritmus pro MAXCUT.

Shannonova kapacita a Lovászova theta-funkce. Barvení tříbarevných grafů.

Maximalizace kvadratických forem na grafu. Problémy splnitelnosti.

angličtina

Poslední úprava: T_KAM (18.04.2010)

Cone programming, duality. Overview of algorithms for semidefinite programming. The Goemans-Williamson MAXCUT algorithm. Shannon capacity and Lovasz theta function. Coloring 3-chromatic graphs. Maximizing quadratic forms on graphs. Constraint satisfaction problems.