Posts

Since I started in November, I have been reading some relevant literature on approximations of the Stability Number of a graph via SDP relaxations. Last week, as a part of the Polynomial Optimization Reading Group (at CWI), I presented the talk: Approximations for the Stability Number. Specifically, I presented some results about the de Klerk Pasechnik Hierarchy. Some relevant literature is: Semidefinite Approximations for the Stability Number of a Graph via Sum of Squares. M.Laurent, N. Gvozdenovic. SIAM Journal of Optimization, 2006 Approximating the stability number of a graph via copositive programming. De Klerk, E.Pasechnik. SIAM Journal of Optimization, 2006 I would like to share with you one proof (slighly changed) of a stronger version of the Polya Theorem presented by M. Laurent, E. de Klerk and P. Parrilo in “ A PTAS for the minimization of polynomials of fixed degree over the simplex ” Theoretical Computer Science: The journal of the EATCS .. 2 006 This