Homework 4

This homework covers the material from lectures 14 to 17

Due date: July 19th.

PDF version of Homework 4.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

Remember that you are only required to turn in 5 out of the 6 exercises below.

Problem 1 - Corner Points of Minimum Vertex Cover Relaxation (20 points)

Given the LP relaxation for minimum vertex-cover:

\begin{align*} \min \ \ &\sum_{v \in V} c_v \cdot x_v \\ \text{s.t.}\ \ 0 \leq \ &x_v \leq 1 \ \text{ for all } v \in V \\ x_u + \ &x_v \geq 1 \ \text{ for all } \{u,v\} \in E \end{align*}

1. Let $y$ be any feasible solution for the LP. Define another solution $y^+$ by: $$y^+_v = \begin{cases} y_v + \varepsilon \ \text{ if } 1/2 < y_v < 1, \\ y_v - \varepsilon \ \text{ if } 0 < y_v < 1/2, \\ y_v\ \ \ \ \ \ \text{ if } y_v \in \{0, \frac{1}{2}, 1\}. \end{cases} $$ Similarly define the solution $y^-_v$, by replacing $\varepsilon$ with $-\varepsilon$.

   Prove that one can find $\varepsilon > 0$ such that both $y^+, y^-$ are feasible for the LP above.

2. Show that every extreme point $z$ of the LP above is half-integral, that is $z_v \in \{0, \frac{1}{2}, 1\}$ for all $v \in V$.

3. Based on the previous parts, design a 2-approximation algorithm for minimum vertex cover.

Problem 2 - Integer Linear Programming Rounding (20 points)

Given a hypergraph $G(V, E)$ where each hyperedge $e \in E$ is a subset of $V$ , our goal is to color the vertices of $G$ using $\{ -1, +1 \}$ such that each hyperedge is as balanced as possible. Formally, given a coloring $\gamma : V \to \{-1, +1\}$ on the vertices, we define $$ \Delta(e) = \sum_{v \in e} \gamma(v) $$
and $$\Delta(G) = \max_{e \in E} |\Delta(e)|.$$ Prove that if the maximum degree of the hypergraph is $d$ (i.e. each vertex appears in at most $d$ hyperedges), then there is a coloring with $$\Delta(G) \leq 2d - 1.$$

Hint: You may find it useful to consider the following LP, where initially we set $B_e = 0$ for all $e \in E$.

\begin{align*} &\sum_{v \in e} x_v = B_e \ \text{ for all } \ e \in E \\ &-1 \leq x_v \leq 1 \ \text{ for all } \ v \in V \end{align*}

Hint 2: check out the problem solving session video to see a definition of basic solution for the LP above.

Problem 3 - Integer Linear Programming Rounding (20 points)

Consider the following maximum covering problem. Given a graph $G$ and a given number $k$, find a subset of $k$ vertices that touches the maximum number of edges.

Let $OPT(G, k)$ be the optimal number of edges touched in $G$ by a set of at most $k$ vertices.

Design an integer programming formulation for the problem, and then find a randomized rounding procedure for the corresponding linear programming relaxation, such that for given $G$ and $k$, it identifies a set of at most $2k$ vertices that touches at least $c \cdot OPT(G, k)$ edges, for some constant $c > 0$.

Your algorithm should always output a set of at most $2k$ vertices, and succeed with probability at least $1/2$.

Helpful fact: you can use the fact that $e^{-x} \leq 1 - (1-1/e)x$ for $0 \leq x \leq 1$. This follows from convexity of $e^{-x}$.

Problem 4 - Strong Duality in SDPs (20 points)

1. Let $\alpha \geq 0$ and consider the following SDP: \begin{align*} \text{minimize } \ \ &\alpha \cdot X_{11} \\ \text{s.t.}\ \ X_{22} &= 0, \\ X_{11} &+ 2 \cdot X_{23} = 1, \\ X &\succeq 0 \end{align*}

   Where $X$ is a $3 \times 3$ symmetric matrix. Prove that the dual of the SDP above is: \begin{align*} \text{maximize } \ \ &y_2 \\ \text{s.t.}\ \
   \begin{pmatrix} y_2 & 0 & 0 \\ 0 & y_1 & y_2 \\ 0 & y_2 & 0 \end{pmatrix} &\preceq \begin{pmatrix} \alpha & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \end{align*}

2. What is the value of the first SDP of part (1)?

3. What is the value of the dual (second SDP) of part (1)?

4. Now consider the following SDP: \begin{align*} \text{minimize } \ \ &x \\ \text{s.t.}\ \
   \begin{pmatrix} x & 1 \\ 1 & y \end{pmatrix} &\succeq 0 \end{align*} Compute its dual program.

5. Is the primal from part (4) strictly feasible? Is the dual strictly feasible?

6. What can you say about strong duality of the SDPs of parts 1 and 4? Are the results consistent with Slater conditions presented in class?

Problem 5 - Projections of Spectrahedra (semidefinite representations) (20 points)

1. Spectrahedra are always closed sets. That is, if a sequence of points $\{p_n\}_{n \geq 0}$ in the spectrahedron converges to a point $p$, then $p$ is also in the spectrahedron.
   Find an example of projected spectrahedron which is not a closed set.

2. The $k$-ellipse with foci $(u_1, v_1), \ldots, (u_k, v_k) \in \mathbb{R}^2$ and radius $d \in \mathbb{R}$ is the following curve in the plane: $$ \left\{ (x,y) \in \mathbb{R}^2 \ \bigm| \ \sum_{i=1}^k \sqrt{(x-u_i)^2 + (y-v_i)^2} = d \right\} $$

   Let $\mathcal{C}_k$ be the region whose boundary is the $k$-ellipse. That is, $\mathcal{C}_k$ is the set: $$ \left\{ (x,y) \in \mathbb{R}^2 \ \bigm| \ \sum_{i=1}^k \sqrt{(x-u_i)^2 + (y-v_i)^2} \leq d \right\} $$

   Find a semidefinite representation (i.e. projection of a spectrahedron) of the set $\mathcal{C}_k$, and prove that your semidefinite representation is correct. That is, that it captures exactly the set $\mathcal{C}_k$ above.

Problem 6 - Challenge to a Dual (20 points)

Let $G(V,E)$ be a graph, where $n = |V|$. For each $i \in V$, let $v_i \in \mathbb{R}^n$ be a vector variable associated to vertex $i$. Consider the following SDP:

\begin{align*} \min \ \ &t \\ \text{s.t.}\ \ \langle v_i , v_j \rangle &= t \ \text{ for all } i \neq j \in V, \ \{i,j\} \not\in E \\ \langle v_i, v_i \rangle &= 1 \ \text{ for all } i \in V \end{align*}

Let $\Theta \in \mathbb{R}$ be the optimum value of the SDP above.

1. Show that the following SDP has optimal value $- \Theta$: \begin{align*} \max \ \ &\langle X, e_{n+1} e_{n+1}^T \rangle \\ \text{s.t.}\ \ \langle X , e_i e_j^T \ &+ e_{n+1} e_{n+1}^T \rangle = 0 \ \text{ for all } i \neq j \in V, \ \{i,j\} \not\in E \\ \langle X , e_i e_i^T \rangle &= 1 \ \text{ for all } i \in V \\ &X \succeq 0 \end{align*} Where $X$ is a $(n+1) \times (n+1)$ symmetric matrix, and $e_1, \ldots, e_{n+1}$ are the elementary unit vectors.

2. Write down the dual of the SDP from part (a).

3. Conclude that the dual you just derived is equivalent to the following SDP:

   \begin{align*} \min \ \ &\sum_{1 \leq i \leq n} Z_{ii} \\ \text{s.t.}\ \ &Z_{ij} = 0 \ \text{ for all } i \neq j \in V, \ \{i,j\} \in E \\ &\sum_{i \neq j} Z_{ij} \geq 1 \\ &Z \succeq 0 \end{align*}

   Where $Z$ is an $n \times n$ symmetric matrix.

4. Rearrange the above SDP to show that the following SDP have value $\dfrac{\Theta-1}{\Theta}$:

   \begin{align*} \max \ \ &\sum_{i,j \in V} Y_{ij} \\ \text{s.t.}\ \ &Y_{ij} = 0 \ \text{ for all } i \neq j \in V, \ \{i,j\} \in E \\ &\sum_{1 \leq i \leq n} Y_{ii} = 1 \\ &Y \succeq 0 \end{align*}

   Where $Y$ is an $n \times n$ symmetric matrix.

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)

Problem 1

From lecture 14, slide 23: prove that the three definitions of corner points of a polytope are equivalent.