**Fact**: An edge can be on only path of the KMW-T. If it lies in a prime node, then there exists a ZC.

The scheduling matrix, can be constructed in other ways, like using KMW method (one LP call per edge) or KS method (n*logn LP calls).

**To Do**: Weak separation oracle from Lovasz's lecture notes (and also GLS:Grotschel-Lovasz-Schrijver book?). How to add quadratic constraints still preserving semidefiniteness.

--

**SDP duality**holds only under some

**regularity conditions**. What are they?

--

To Do:

**SDP in mails**

--

A Linear program is trivially a SDP. If a constraint of a LPP is of the form <= p, we can define a diagonal matrix A with A_i,i = a_i and we can also define a variable matrix X_i,i = x_i The resultant program is a SDP.

--

We could do a similar thing with the vectors q or X.

**What about the vector (1,-1) for the edges?**The 2nd eigen values are non-+ve. which means that we cannot directly use that value. However, SDP only requires that the variable matrices are SD. not their coefficients.

--

Is this a SDP?

max sum_e z_e

z^2 <= 1

--

**To do**look up the different SDP formulations from Lovasz's notes.