COMPUTER SCIENCE TRIPOS Part II – 2019 – Paper 9
Advanced Algorithms (tms41)
(a) Consider the definition of an approximation algorithm.
(i) Explain the meaning of approximation ratio in the case of a maximisation
problem. [2 marks]
(ii) How is this definition adjusted to the case of a randomised approximation
algorithm? [2 marks]
(b) State the definition of PTAS and FPTAS. [4 marks]
(c) Let G = (V, E) be an undirected graph. For any k ≥ 1, define G(k)
to
be the undirected graph (V
(k)
, E(k)
), where V
(k)
is the set of all ordered
k-tuples of vertices from V and E
(k)
is defined so that (v1, v2, . . . , vk) is
adjacent to (w1, w2, . . . , wk) if and only if {v1, v2, . . . , vk, w1, w2, . . . , wk} forms a
clique.
(i) Argue that the graph G(k)
can be constructed in time polynomial in n (for
any fixed value of k). [3 marks]
(ii) Prove that the size of the maximum clique in G(k)
is equal to the k-th power
of the size of the maximum clique in G. [5 marks]
(iii) Argue that if there is a polynomial-time approximation algorithm that has
a constant approximation ratio for finding a maximum clique, then there is
a polynomial-time approximation scheme (PTAS) for the problem.
Hint: Your PTAS should be based on applying the given approximation
algorithm with constant approximation ratio to G(k)
for a proper choice of
k > 0. Then use the equivalence in part (ii) to analyse its approximation
ratio. [4 marks]