COMPUTER SCIENCE TRIPOS Part II – 2016 – Paper 9
Advanced Algorithms (TMS)
(a) Explain the difference between PTAS and FPTAS, and give one example of a
problem for which a FPTAS is known, and one example of a problem for which
a PTAS is known but no FPTAS. [4 marks]
(b) We consider an extension of the MAX-3-CNF problem, called MAX-4-CNF
problem, where we are given a 4-CNF formula with m clauses, e.g., (x1 ∨ x3 ∨
x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ x5) ∧ · · · , and the goal is to find an assignment of the
variables x1, x2, . . . , xn that satisfies as many clauses as possible.
(i) Design a randomised approximation algorithm and analyse its approximation ratio. (For full marks, the approximation ratio must be smaller than
10/9.) [4 marks]
(ii) Express the MAX-4-CNF problem as an integer program. [4 marks]
(iii) Based on the construction from Part (b)(ii) or otherwise, describe an
algorithm that performs randomised rounding on the solution of a linear
relaxation. [3 marks]
(iv) Analyse the expected approximation ratio of the algorithm from Part
(b)(iii).
Hint: You may want to use the following two inequalities. Firstly, for any
non-negative numbers a1, a2, . . . , ak, we have
Y
k
i=1
ai
!1/k
≤
Pk
i=1 ai
k
.
Secondly, for any integer k ≥ 2 and 0 ≤ a ≤ 1,
1 −

1 −
a
k
k
≥

1 −

1 −
1
k

k

·