2
$\begingroup$

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:

Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.

Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.

For every edge $e$ in $e_1,e_2,...,e_m$ if both endpoints of e are not contained in $B_0$, then flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

I have already proved that this algorithm has $E[|B_0|] \le 2|OPT|$.

Now I don't know how to apply the method of conditional expectations (defined here) to derandomize the algorithm in order to show that we can't obtain an efficient deterministic version and that gives the same result of the expected value found previously. Can you show me to do this?

$\endgroup$
7
  • $\begingroup$ Sorry but I didn't understand your first point. For the second one, yes, I meant that $\endgroup$ Jan 1, 2020 at 16:56
  • $\begingroup$ Can you add a sketch of your proof that $E[|B_0|] \le 2 |OPT|$, so we can check it? Also applying the method of conditional probabilities requires knowing the particulars of the proof. $\endgroup$
    – Neal Young
    Jan 1, 2020 at 17:35
  • $\begingroup$ Here it is comp.nus.edu.sg/~stevenha/cs4234/lectures/01.VertexCover.pdf I want to apply the method of conditional expectations to show that it gives the same result but it has less efficiency than randomized one $\endgroup$ Jan 1, 2020 at 17:59
  • $\begingroup$ I forgot to say, chapter 5.2. I did something like that $\endgroup$ Jan 1, 2020 at 18:15
  • 2
    $\begingroup$ That proof in the notes linked to in the comment (Section 5.2) has a technical problem (a gap). $E'$ is itself a random variable, but the top of page 11 writes $E[\sum_{e\in E'} X_e] = \sum_{e\in E'} E[X_e]$. But the sum on the right is a random variable, since $E'$ is, so this equation makes a category error. Also note that $E'$ is not independent of the $X_e$'s, so some care is needed. The proof should probably use something like Wald's equation (or a more careful accounting of conditioning) to fix the issue. $\endgroup$
    – Neal Young
    Jan 2, 2020 at 1:11

2 Answers 2

3
$\begingroup$

First, let us repeat the analysis of the algorithm.

Fix some optimal vertex cover OPT, with cost $O$.

Let $S$ be the cost of the vertex cover produced by the algorithm.

Let $A_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex belonging to OPT", and let $A = \sum_e A_e$.

Let $B_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex not belonging to OPT", and let $B = \sum_e B_e$.

Thus $S = A+B$ and $A \leq O$.

The idea of the analysis is that $\Pr[B_e] \leq \Pr[A_e]$. To see this, consider what happens when vertex $e$ is considered. If $e$ is already covered by vertices already chosen, then $A_e = B_e = 0$. If both endpoints of $e$ belong to OPT, then $A_e = 1$ and $B_e = 0$. Otherwise, $\Pr[A_e] = \Pr[B_e] = 1/2$. In all cases, $\Pr[B_e] \leq \Pr[A_e]$.

Since $\Pr[B_e] \leq \Pr[A_e]$, we have $\mathbb{E}[B] \leq \mathbb{E}[A]$. Therefore $$ \mathbb{E}[S] = \mathbb{E}[A+B] \leq 2\mathbb{E}[A] \leq 2O. $$

How would we apply the method of conditional expectations? Here are two options:

  1. Given the choice of which endpoint is taken, compute the expected value of $S$. If $z \in \{x,y\}$ was chosen, then we remove all edges adjacent to $z$, and then run the algorithm as usual. This reduces the problem to computing $\mathbb{E}[S]$, which is the expected number of edges which are not covered when their time comes. It's not so clear how to compute $\mathbb{E}[S]$.

  2. The same, but instead of computed $\mathbb{E}[S]$ exactly, compute an approximation which is good enough to obtain a 2-approximation. Let $O_z$ be the optimum solution after removing all edges adjacent to $z$. Then $$ \mathbb{E}[S \mid x] \leq 1 + 2O_x, \quad \mathbb{E}[S \mid y] \leq 1 + 2O_y. $$ If $x$ belongs to OPT then $O_x = O-1$, and otherwise $O_x \leq O$. Thus the average of both bounds is at most $$ \frac{1+2(O-1)+1+2O}{2} = 2O, $$ since at least one of $x,y$ belongs to OPT. Therefore, if we choose the vertex that minimizes $O_x,O_y$, then the resulting algorithm will produce a 2-approximation. Unfortunately, it's not clear how to compute $O_x,O_y$ (indeed, this ought to be hard).

In summary, it's not so clear how to apply the method of conditional expectations.

$\endgroup$
1
$\begingroup$

Here are two possible derandomizations of the algorithm, with some caveats.

One possible derandomized algorithm


  1. compute an optimal fractional solution $x^*$ to the standard linear-program (LP) relaxation: $$\begin{align} \textsf{minimize } \sum_{v\in V} x_v \\ x_u + x_w \ge 1 &&& ((u, w) \in E) \\ x_v \ge 0 &&& (v\in V) \end{align} $$

  2. fix some order $e_1, e_2,...,e_m$ over all edges in the edge set $E$ of $G$, and set $B_0=\emptyset$

  3. for every edge $e_i$ in $e_1,e_2,...,e_m$, if both endpoints of $e_i$ are not in $B_0$:

  4. $~~~$ add $v = \arg\max \{x^*_v : v\in e_i\}$ to $B_0$ (add the endpoint with larger weight in $x^*$)

  5. return $B_0$


Correctness. The algorithm returns a vertex cover because the loop maintains the invariant that all edges considered so far have an endpoint in $B_0$.

Proof of 2-approximation. We claim the algorithm maintains the invariant $$|B_0| \le 2 \sum_{v\in B_0} x^*_v.$$ The invariant holds initially when $B_0=\emptyset$. In each iteration $t$, when it considers the edge $(u,w)=e_t$, the algorithm chooses the endpoint $v\in \{u,w\}$ that maximizes $x^*_v$, so that the increase in $|B_0|$ is 1, while the increase in $2\sum_{v\in B_0} x^*_v$ is $$2\max(x^*_u, x^*_w) \ge x^*_u + x^*_w \ge 1.$$ (The last inequality follows from the LP constraint $x^*_u + x^*_w \ge 1$ for all $(u, w) \in E$.)

At termination the invariant implies $$|B_0| \le 2\sum_{v\in B_0} x^*_v \le 2\sum_{v\in V} x^*_v \le 2\textsf{OPT},$$ as the cost $\sum_{v\in V} x^*_v$ of the optimal LP solution is a lower bound on $\textsf{OPT}$.

Discussion

We derive the above algorithm by strengthening the original analysis, which proves the approximation ratio via the hard-to-compute OPT, by an analysis that proves the approximation ratio via the easier-to-compute fractional optimum $x^*$ (which then lower-bounds OPT). We then apply the method of conditional probabilities to the strengthened analysis. In each iteration, the original algorithm's random choice of endpoint is replaced by a deterministic choice that keeps the conditional expectation of the final value of $|B_0| - 2\sum_{v\in B_0} x^*_v$ below zero. The resulting derandomized algorithm, shown above, depends on $x^*$.

A derandomized algorithm that doesn't depend on $x^*$

We can remove the dependence on $x^*$ by replacing $x^*$ by an appropriate dual solution $y$, computed greedily by the algorithm:


  1. initialize $y$ to be an all-zero solution to the dual of the standard LP relaxation: $$\begin{aligned} \textsf{maximize } \sum_{e\in E} y_e \\ \sum_{e \ni v} y_e \le 1 &&& (v\in V)\\ y_e \ge 0 &&& (e\in E) \end{aligned} $$

  2. define $T(y) = \{v\in V : \sum_{e\ni v} y_e = 1\}$ to contain the vertices with tight dual constraints

  3. fix some order $e_1, e_2,...,e_m$ over all edges in the edge set $E$ of $G$, and set $B_0=\emptyset$

  4. for every edge $e$ in $e_1,e_2,...,e_m$, if both endpoints of $e$ are not in $B_0$:

  5. $~~~$ if $e \cap T(y) = \emptyset$:

  6. $~~~~~~$ set $y_{e} \gets 1$ (this makes $e\subseteq T(y)$)

  7. $~~~$ add to $B_0$ an endpoint of $e$ in $T(y)$

  8. return $B_0$


Correctness. The algorithm returns a vertex cover because the loop maintains the invariant that all edges considered so far have an endpoint in $B_0$.

Proof of 2-approximation. We claim the algorithm maintains the invariant $$|B_0| \le \sum_{e\in E} |B_0\cap e|\, y_e.~~~~~~(1)$$ The invariant holds initially when $B_0=\emptyset$. When the algorithm adds an endpoint $v\in e\cap T(y)$ to $B_0$ in Step 6, the left-hand side $|B_0|$ of (1) increases by 1, while the right-hand side of (1) increases by $$\sum_{e'\in E} |\{v\}\cap e'| y_{e'} = \sum_{e'\ni v} y_{e'},$$ which equals 1 because $v$ is in $T(y)$. So the invariant is preserved. At termination the invariant implies $$|B_0| \le \sum_{e\in E} 2 y_e.$$ That is, the size of $B_0$ is at most twice the cost of the dual solution $y$. By inspection of the algorithm, the dual solution is feasible, so the cost of $y$ is a lower bound on $\textsf{OPT}$. So the algorithm gives a 2-approximation. $~~~~\Box$

Remark

The latter algorithm does not necessarily keep the conditional expectation of the final cover returned by the original algorithm below $2\textsf{OPT}$. Indeed, consider a star graph with root $r$ with three children $a, b, c$. Suppose the algorithm considers the edges in order $(r, a)$, $(r, b)$, $(r, c)$. The first step of the algorithm can choose to add $a$ to the cover $B_0$. However, the conditional expectation of the original randomized algorithm's cost, given that it first chooses $a$, then exceeds $2 = 2\textsf{OPT}$ (because the latter algorithm will then always choose at least 2 vertices, and in some outcomes will choose 3).

This underscores that when we apply the method of conditional probabilities, we apply it to a particular proof of the approximation ratio of an algorithm, not directly to the algorithm itself.

On the other hand, it still feels somewhat unsatisfactory, as it's not quite clear what proof we are derandomizing to obtain the last algorithm above. It seems we are applying not just derandomization, but also the meta-principle that invariants that are shown to hold with respect to some optimal primal solution can often be recast to be shown via some implicit dual solution. It would be nice to have a more general understanding of this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.