Final Exam Reviews

Your final exam will be on Monday 05/04 from 1-4pm in WeH 7500. As usual, the exam is open-book, open-notes, etc. You should expect 6 - 8 questions, covering everything we have done in this class (but focusing on the materials after Midterm 2).

Here's the practice final we went over in class today (PDF). We ran out of time in the end, but there are a couple of things I wish I had time to talk about, so I'll just blog it here (hoping it will be useful when you study for the final).

A 2-approximation for the Steiner Tree Problem. Given a graph $G = (V, E)$ and a set of terminals $T \subseteq V$, we want to find a minimum-weight subgraph $S \subseteq G$ that connects all the terminals. This problem is known to be NP-hard, so we look for an approximation algorithm. Consider the following simple algorithm:

(1) construct a metric completion $G'$ of the graph $G$ on just the vertices of $T$,
(2) compute an MST $ST$ on $G'$,
(3) return $\widehat{S} = \cup_{e \in ST} \phi(e)$ (if you want your solution to be a tree, break cycles as necessary).

The metric completion $G'$ is basically a complete graph on $|T|$ nodes, where the weight on the edge between $u$ and $v$ is the distance of the shortest path between $u$ and $v$ in the original graph $G$. The function $\phi(u, v)$ returns the set of edges on the shortest path (in fact any shortest path) connecting $u$ and $v$.

Claim: $\widehat{S}$ is a feasible solution.

By construction, it is easy to see that $\widehat{S}$ (before we break any cycle) connects all the terminal pairs. Note that breaking cycles doesn't affect connectivity.

Claim: $\widehat{S}$ is a $2$-approximation.

Let $S^*$ be an optimal Steiner tree solution. Consider an Euler's tour $ET = \langle v_1, v_2, ..., v_{2|T|} \rangle$ on $S^*$ (with each edge doubled). Note that each original edge is traversed exactly twice, so $w(ET) = 2w(S^*)$. Create a new tour $ET'$ by dropping non-terminal vertices, and vertices that showed up earlier in the tour sequence. Thus $ET'$ contains distinct vertices, and $ET'$ is a spanning tree (we don't go back to where we started because that vertex already showed up in the tour). Furthermore, the weight of $ET'$, denoted by $w(ET')$, is at most $w(ET)$ by the triangle inequality. Since $ET'$ is a spanning tree, it cannot have a lower weight than the minimum spanning tree: $w(MST) \leq w(ET')$. Combining these little pieces together, we have $w(MST) \leq w(ET') \leq w(ET) = 2w(S^*)$. Finally, we observe that $w(\widehat{S}) \leq \sum_{e \in MST} w(\phi(e)) = w(MST)$, and hence $w(\widehat{S}) \leq 2w(S^*) = 2OPT$.