COMPUTER SCIENCE TRIPOS Part II – 2021 – Paper 9
Advanced Algorithms (tms41)
(a) Assume you have a randomised approximation algorithm for a maximisation
problem, and your algorithm achieves an approximation ratio of 2. What can
you deduce for
E[C
∗
/C],
where C
∗
is the cost of the optimal solution, C is the cost of the solution of the
approximation algorithm, and E[.] denotes the expectation? [4 marks]
(b) Consider the following optimisation problem on graphs: Given an undirected,
edge-weighted graph G = (V, E, w) with w : E → R
+, we want to find a subset
S ⊆ V such that w(S, V \ S) = P
e∈E(S,V \S) w(e) (the total sum of weights over
all edges between S and V \ S) is maximised.
(i) Design a polynomial-time approximation algorithm for this problem. Also
analyse its running time and prove an upper bound on the approximation
ratio. [8 marks]
(ii) Find a graph which matches your upper bound on the approximation ratio
from Part (b)(i) as closely as possible. [4 marks]
(iii) Consider now the following generalisation of the problem. Given an integer
k ≥ 2, we want to partition V into disjoint subsets S1, S2, . . . , Sk so that
we maximise
X
k
i=1
w(Si
, V \ Si).
Describe an extension of your algorithm in Part (b)(i). What approximation ratio can you prove for this algorithm? [4 marks]