Homework 3

This homework covers the material from lectures 13 to 18.

Due date: June 26th, 10pm Waterloo time.

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

Required Exercises

Problem 1 - Corner Points of Minimum Vertex Cover Relaxation (15 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 (15 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$.

Problem 3 - 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 4 - 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.

Problem 5 - SDP relaxation (10 points)

Given a 3-uniform hypergraph $G(V, E)$ (that is, a hypergraph where each hyperedge has exactly 3 vertices), we say that a 2-coloring of $V$ is valid for a hyperedge $e = \{ a, b, c\} \in E$ if the hyperedge $e$ is not monochromatic upon this coloring.

The Max-2C3U problem is the following:

• Input: a 3-uniform hypergraph $G(V, E)$
• Output: a 2-coloring of the vertices of $G$ of maximum value, that is, a function $f : V \rightarrow \{ -1, 1 \}$ (the coloring) which maximizes the number of valid hyperedges.

In this question, you are asked to:

2.1. Write the optimization problem above as a quadratic program

2.2. Formulate an SDP relaxation for the problem, and prove that it is in fact a relaxation

Problem 6 - Competitive Analysis (20 points)

You have reached a river (modelled as a straight line) and must find a bridge to cross it. The bridge is at some integer coordinate upstream or downstream.

1. Give a 9-competitive deterministic algorithm for optimizing the total distance travelled up and downstream before you find the bridge.
2. Give a randomized 7-competitive algorithm for the problem

Problem 7 - Multiplicative Weights Update (20 points)

Here is a variation on the deterministic Weighted-Majority algorithm, designed to make it more adaptive.

1. Each expert begins, on the 1st day, with weight $1$.
2. We predict the result of a weighted-majority vote of the experts.
3. If an expert makes a mistake, we penalize it by dividing its weight by $2$, but only if its weight was at least $1/4$ of the average weight of experts.

Prove that in any contiguous block of trials (e.g., the block from 51st day through the 77th day), the number of mistakes made by the algorithm is at most $O(m + \log n)$, where $m$ is the number of mistakes made by the best expert in that block, and $n$ is the total number of experts.

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 - Integer Linear Programming Rounding (Advanced Problem)

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*}

Guidance on how to use the hint:

1. The main approach will be to iteratively update the LP above to try and find our desired solution. At each iteration, we will use a solution of the LP to guide us.
2. What does the LP given in the hint give us? What is captured by solutions to the LP?
3. What are the basic solutions to the LP above? How do we find a basic solution?
4. Now that we have a basic solution, and know how they look, we can prove the following consequence of basic solutions $$x \text{ is basic } \implies \{A_i\}_{i \in \text{supp}^*(n)} \text{ is L.I. where } \text{supp}^*(x) = \{i \in [n] \mid x_i \in (-1, 1)\}$$
5. What happens if a coordinate is not in $\text{supp}^*(x)$?
6. What happens when we cannot update the LP?
7. How do we get unstuck? Hint: Throw away a constraint. Which one?
8. At most how many vertices will THE deleted hyperedge have?
9. What is the worst that can happen to an edge in this process?

Problem - Projections of Spectrahedra (semidefinite representations)

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 - Spectrahedra and Projections (Advanced Problem)

This problem requires basic knowledge of real analysis and topology.

1. Both spectrahedra and projected spectrahedra are convex sets. Show that spectrahedra are always closed sets.

2. 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.

Problem - Paging Algorithms

A conservative algorithm is one that makes at most $k$ page faults on any consecutive subsequence of the input that contains at most $k$ pages. Here $k$ is the size of the cache.

1. Prove that LRU and FIFO are conservative
2. Prove that any conservative algorithm is k-competitive.

Problem - Multiplicative Weights and Max-Flow (More advanced)

Consider the maximum flow problem from $s$ to $t$ on a directed graph, where each edge has capacity one. A fractional $s$-$t$ flow solution with value $k$ is an assignment of each edge $e$ to a fractional value $x(e) \in \mathbb{R}$, satisfying

$$ \begin{align*} \sum_{e \in \delta^{out}(s)} x(e) &= \sum_{e \in \delta^{in}(t)} x(e) = k \\ \sum_{e \in \delta^{in}(s)} x(e) &= \sum_{e \in \delta^{out}(t)} x(e) = 0 \\ \sum_{e \in \delta^{in}(v)} x(e) &= \sum_{e \in \delta^{out}(v)} x(e) \ \ \forall v \in V \setminus \{ s, t \} \\ 0 &\leq x(e) \leq 1, \ \ \forall e \in E \end{align*} $$

Use the multiplicative weights update method to solve this Linear Program by reducing the flow problem to the problem of finding shortest paths between $s$ and $t$. Analyze the convergence rate and total complexity of your algorithm to compute a flow of value $k \cdot (1-\epsilon)$ for any $\epsilon > 0$.