MIT 6.854 Spring 2016 Lecture 19: Semidefinite Programming, MAXCUT

[@aleksagordic9593]

4:50 - 13:30 MAXCUT problem (phrasing it as an (fractional) LP doesn't solve it more precisely than naive approximation algo with flipping a fair coin) 13:30 - 23:30 positive semidefinite (PSD) definition and SDP (semidefinite programming) 23:30 - 35:40 building intuition 35:40 - 41:20 lemma 1 (used for proving weak duality and another way of defining what a PSD is) 43:35 - 46:35 lemma 2 aka weak duality 47:15 - 49:50 strong duality "usually" holds (Slater's condition) 50:45 - 58:10 MAXCUT problem now solved using SDP 58:10 - 1:12:30 Goemans-Williamson theorem/analysis 1:12:30 UGC - unique game conjecture

[@yoavtamir7707]

thanks

[@김동원-n6b]

thanks too

[@wuzhai2009]

Students in this class are well prepared.

[@zed625]

Max cut is finished around 13:20