COMPUTER SCIENCE TRIPOS Part II – 2019 – Paper 8
Advanced Algorithms (tms41)
(a) For each of the following claims, state whether it is true or not and give a brief
justification.
(i) For any linear program with n variables and m constraints, there are at
most
n+m
m


different basic solutions. [2 marks]
(ii) The Simplex Algorithm has a worst-case polynomial runtime. [2 marks]
(iii) In each iteration of the Simplex Algorithm, the value of the objective
function changes. [2 marks]
(iv) The auxiliary linear program in Initialize-Simplex always has a feasible
solution. [2 marks]
(v) The fundamental theorem of linear programming also holds if linear
constraints are allowed to be strict. [2 marks]
(vi) The set of feasible solutions of any linear program forms a convex set.
[2 marks]
(b) For the following linear program, write down the auxiliary linear program used
by Initialize-Simplex in slack form: [3 marks]
minimize − 4×1 + x2
subject to − 4×1 + 2×2 ≥ −4
x1 − 6×2 ≤ −3
(c) Recall the algorithm for the unweighted vertex cover problem that is based on
rounding the solution of a linear program.
(i) What is the approximation ratio of this algorithm? [1 mark]
(ii) Give an example of a graph and the corresponding linear program for which
the gap between the linear program solution and optimal solution is as large
as possible