COMPUTER SCIENCE TRIPOS Part II – 2017 – Paper 7
Advanced Algorithms (TMS)
(a) Into what three cases can a linear program in standard form be classified?
[3 marks]
(b) Consider the (unweighted) vertex cover problem for the graph G = (V, E) with
V = {1, 2, 3} and E = {{1, 2}, {2, 3}, {1, 3}}.
(i) Write down the linear program relaxation for the vertex cover problem and
solve the linear program. [6 marks]
(ii) Based on the solution of the linear program in (b)(i), derive an integer
solution using the rounding approach described in the lecture. [2 marks]
(c) Consider the following randomised algorithm for the unweighted vertex cover
problem:
Initialize S to be the empty set
For all edges e=(u,v) do
If neither u nor v belongs to S
Randomly choose u or v with probability 1/2
and add the vertex to S
End If
End For
Return S
Derive an upper bound, as tight as possible, on the approximation ratio of the
algorithm.
Hint: Try to find an invariant that bounds from below the size of the intersection
of the current solution S = S(i) with the optimum solution, where S(i) denotes
the set S after the i-th iteration of the FOR loop. [9 marks]