Advanced Algorithms · Quiz 2 · 6 Aug 2023 · May 2023 term

Question 15: Consider a different rounding strategy for the LP relaxa…

Question 15

+5 marksOne correct option

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 = \{v_1, \ldots, v_n\}$ and we denote the associated variable of $v_i$ by $x_i$ then the cover $C$ is computed as follows:

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

Which statement is true?

A
This does not work, because we might report an invalid solution.
B
This gives a valid solution, but the approximation ratio becomes worse.
C
This gives a valid solution, and in fact the solution is always exactly the same as in the original rounding scheme.
D
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 - ϵ for any ϵ > 0.
E
This gives a valid solution, and the approximation ratio of the algorithm becomes 3/2.

Show answer

Correct answer

D
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 - ϵ for any ϵ > 0.

See the whole paper Take it as a mock test

Question 15 of 15 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 6 Aug 2023, in the May 2023 term (IIT M DEGREE AN3 EXAM QPE3 06 Aug 2023). It carries 5 marks.

Question 15: Consider a different rounding strategy for the LP relaxa…

Question 15

More questions from this paper