CS614. Advanced Algorithms. L06 Quiz.

CS614. Advanced Algorithms.

L06 Solutions

Back to the course page

Acknowledgement

The questions in this problem set are adapted from the Coursera course on Approximation Algorithms taught by Mark de Berg.

Problem 1. Changing the threshold

Consider the algorithm LPAPX-WVC from the class.

Problem 1.1 Increasing the threshold

Suppose that instead of putting a vertex \(v_i\) into the cover when \(x_i \geqslant 1/2\), we put \(v_i\) into the cover when \(x_i \geqslant 2/3\). What happens?

  • We still get a valid solution, and the algorithm remains a 2-approximation.
  • We still get a valid solution, and the algorithm becomes a (3/2)-approximation.
  • We still get a valid solution, and the algorithm becomes a 3-approximation.
  • We may no longer get a valid solution.
Problem 1.2 Decreasing the threshold

Suppose that instead of putting a vertex \(v_i\) into the cover when \(x_i \geqslant 1/2\), we put \(v_i\) into the cover when \(x_i \geqslant 1/3\). What happens?

  • We still get a valid solution, and the algorithm remains a 2-approximation.
  • We still get a valid solution, and the algorithm becomes a (3/2)-approximation.
  • We still get a valid solution, and the algorithm becomes a 3-approximation.
  • We may no longer get a valid solution.

If we increase the threshold \(t\) beyond \(0.5\), then the output may not even be a vertex cover: for example, consider the example of a complete graph where the LPOPT sets all variables to \(0.5\): in this case our output will be the empty set with any threshold higher than \(0.5\).

If we decrease the threshold \(t\) below \(0.5\), then the output will be a vertex cover — indeed, if any edge \((u,v)\) is uncovered, then both \(u\) and \(v\) were set to values less than \(t\), and in particular less than \(0.5\), so we will violate our edge constraint just as we do when working with a threshold of \(0.5\). However, by choosing a lower value, we worsen the approximation ratio: in particular, if \(t = 1/3\) then the output is a \(3\)-approximation.

Problem 2. Changing the rounding scheme

Consider a different rounding strategy for the LP relaxation of the vertex cover problem. Instead of rounding up every vertex whose value is at least \(0.5\) after running the LP, we do the following:

We look at every edge, and then we round up the variable of the endpoint with the highest value, where in case of ties we take the endpoint with the highest index.

In other words, if the vertex set is \(V=\left\{v_1, \ldots, v_n\right\}\) and we denote the associated variable of \(v_i\) by \(x_i\) then the cover \(C\) is computed as follows:

\(C:=\left\{v_i \in V:\right.\) there is an edge \(\left(v_i, v_j\right)\) such that \(\left(x_i>x_j\right)\) or \(\left(x_i=x_j\right.\) and \(\left.\left.i>j\right)\right\}\)

Which statement is true?

  • This does not work, because we might report an invalid solution.
  • This gives a valid solution, but the approximation ratio becomes worse.
  • This gives a valid solution, and in fact the solution is always exactly the same as in the original rounding scheme.
  • This gives a valid solution. We sometimes report a better solution than in the original rounding scheme, but the approximation ratio of the algorithm is still more than \(2 - \epsilon\) for any \(\epsilon > 0\).
  • This gives a valid solution, and the approximation ratio of the algorithm becomes \(3/2\).

The solution is valid: indeed, let \((u,v)\) be an edge, and recall that the algorithm worked as follows:

We look at every edge, 
and then we round up the variable of the endpoint with the highest value, 
where in case of ties we take the endpoint with the highest index.

Since one of the endpoints was rounded up, the edge is covered; and this is evidently true of every edge.

The solution with respect to this rounding may be better than the threshold-based rounding: for example, consider again a complete graph where the LPOPT sets all variables to \(1/2\): the threshold-based rounding leads to a solution of cost \(n\), while the cost here will be strictly less.

However, to see that the approximation ratio of the algorithm is still more than \(2 - \epsilon\) for any \(\epsilon > 0\), consider, for example, a cycle on \(n\) vertices: one can choose a suitably large value of \(n\) to bring the approximation ratio arbitrarily close to \(2\).

Problem 3. Lower Bound

Suppose you have created an algorithm for a certain problem using LP relaxation and you want to say something about its approximation ratio. Which lower bound on the optimal solution can you use?

  • The solution to the 0/1-LP.
  • The solution to the relaxed LP.
  • Depends on the problem.

As was clarified in class, this question is in the context of minimization problems.

The solution to the relaxed LP is a useful lower bound for the OPT. The value of the OPT for the 0/1-LP is exactly equal to the OPT (in a presumed exact formulation of the problem) and does not, by itself, provide information about the behavior of the relaxed LP.

Problem 4. Integrality Gap

What is the integrality gap of the vertex-cover LP for the complete graph on \(n\) vertices, where all vertices have weight 1?

ILPOPT = \(n-1\) and LPOPT = \(n/2\); so the integrality gap is \(2 \cdot (n-1)/n = 2(1 - \frac{1}{n})\).