CSEDays. Theory 2013

Ural Federal University, Ekaterinburg, Russia, June 29 - July 01

News subscription
Share:

Reviews

Для меня это была уже третья школа CSEDays. И, как я и ожидал, она оставила очень позитивные эмоции и дала очередной толчок к тому, чтобы сделать что-то грандиозное в мире Computer Science. Так что, лично я считаю, что школа удалась!
-- / CSEDays. Application 2011
Home / Konstantin Makarychev /

Semidefinite programming and approximation algorithms

Author: Konstantin Makarychev

   Approximation algorithms are used to find approximate solutions to problems that cannot be solved exactly in polynomial time. I will talk about linear programming (LP) and then semidefinite programming (SDP) based approximation algorithms. I will give examples of such algorithms and prove their correctness. Then, we will discuss the connection between approximation algorithms and high dimensional geometry. I will also talk about the Unique Games Conjecture and the limits of approximability.