COMPUTER SCIENCE TRIPOS Part II – 2020 – Paper 9
Advanced Algorithms (tms41)
(a) (i) What is the approximation ratio of an approximation algorithm?
[2 marks]
(ii) State the definitions of PTAS and FPTAS. [4 marks]
(b) Consider the two approximation algorithms for VERTEX-COVER from the lectures (one greedy algorithm and one based on rounding a linear program).
(i) What are the approximation ratios of these two algorithms? [2 marks]
(ii) Construct an input graph that demonstrates the tightness of the approximation ratio of the greedy algorithm (for full marks, your construction
should work for any even number of vertices n). [3 marks]
(c) Consider the following randomised algorithm to compute a solution of the
VERTEX-COVER problem for an unweighted graph G = (V, E):
Let C be the empty set
While E not empty do
Pick any edge e={u,v} from E
Choose x from {u,v} uniformly at random
Add x to C
Remove all edges incident to x from E
End While
Return C
(i) Explain briefly why the set C returned is a valid vertex cover. [2 marks]
(ii) Find a lower bound on the probability that the algorithms returns an
optimal solution.
Hint: For each edge e = {u, v} picked by the algorithm consider the event
that the chosen vertex x ∈ {u, v} added to C is also part of an optimal
cover. [4 marks]
(iii) Given a lower bound p ∈ (0, 1) on the probability that this algorithm
returns an optimal solution, describe a new algorithm that returns an
optimal solution with probability at least δ, for any given δ ∈ [p, 1).
[3 mark