Consider the matrix $M_2(y)$; if this is psd, then we know, e.g., that $y_{abcd}$ can be written as the dot product of vectors $z_{ab}$ and $z_{cd}$, and also as the dot products of vectors $z_{bc}$ and $z_{ad}$ etc. Similarly $y_{ab}$ can be written as $z_{a}$ dot $z_b$, and also as $z_{ab}$ dot $z_\emptyset$. Hence we now have these vectors $z$'s, each subscripted by at most two vertices, with some constraints relating them.

The goal of the problem is to show that the SDP $Q_1(K_{VC})$ is at least as strong as a natural vertex cover SDP, which assigns a vector $v_i$ to each node $i$ to minimize $\sum_i v_i \cdot v_i$ subject to

- $(v_\emptyset - v_a)(v_\emptyset - v_b) = 0$ for all edges $ab$.
- $v_\emptyset \cdot v_\emptyset = 1$ (say).

Does your SDP also imply the triangle inequalities:

- $||v_a - v_b||^2 + ||v_b - v_c||^2 \geq ||v_a - v_c||^2$?

## No comments:

Post a Comment