COMPUTER SCIENCE TRIPOS Part II – 2015 – Paper 7
Advanced Algorithms (TMS)
(a) State the fundamental theorem of linear programming. [3 marks]
(b) Consider the following linear program:
Minimize − 3×1 − 2×2
subject to:
3×1 + x2 ≤ 5
−2×1 ≥ −10 + 4×2
x1, x2 ≥ 0.
(i) Convert this LP into standard and slack form, and specify the initial basic
solution. [4 marks]
(ii) Solve this LP using the simplex algorithm. Specify the associated basic
solution after each iteration. [4 marks]
(c) We consider the Steiner Tree Problem defined as follows. We are given an
undirected, connected graph G = (V, E) with a non-negative cost-function
c : E → R+. Further, we are given a set S ⊆ V of terminals. The goal is
to find a minimum-cost subgraph of G that connects all terminals, where the
cost of a subgraph is the sum of the costs of its edges.
Consider the following algorithm:
• Let H = (V, E0
) be the metric completion of G, where E
0 = {{u, v}: u, v ∈
V } and c({u, v}) is the cost of the shortest path from u to v in G.
• Compute a Minimum Spanning Tree T on the subgraph H[S] induced by
the set of terminals S.
• Replace every edge {u, v} in T by the edges of a shortest path from u to v
in G, and return the solution.
(i) Prove an upper bound of 2(1 −
1
|S|
) on the approximation ratio of this
algorithm.
[Hint: You can use an approach similar to the analysis of Approx-TSPTour.] [6 marks]
(ii) Construct an example which provides a matching lower bound on the
approximation ratio. [3 marks]