91Ó°ÊÓ

Devise a branch-and-bound algorithm for the SET COVER problem. This entails deciding:

(a) What is a subproblem?

(b) How do you choose a subproblem to expand?

(c) How do you expand a subproblem?

(d) What is an appropriate lowerbound

Do you think that your choices above will work well on typical instances of the problem? Why?

Given an undirected graph$\mathit{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$ in which each node has$\mathit{d}\mathit{e}\mathit{g}\mathit{r}\mathit{e}\mathit{e}\mathbf{≤}\mathit{d}$ , show how to efficiently find an independent set whose size is at least$\frac{\mathbf{1}}{\mathbf{d}\mathbf{+}\mathbf{1}}$times that of the largest independent set.

In the MINIMUM STEINER TREE problem, the input consists of: a complete graph $\mathit{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$with distances ${\mathrm{d}}_{uv}$between all pairs of nodes; and a distinguished set of terminal nodes$\mathit{V}\mathbf{\text{'}}\mathbf{⊆}\mathit{V}\mathbf{.}$The goal is to find a minimum-cost tree that includes the vertices $\mathit{V}\mathbf{\text{'}}$. This tree may or may not include nodes in $\mathit{V}\mathbf{-}\mathit{V}\mathbf{\text{'}}$

Suppose the distances in the input are a metric (recall the definition on page 292). Show that an efficient $\mathit{r}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathbf{-}\mathbf{2}$approximation algorithm for MINIMUM STEINER TREE can be obtained by ignoring the nonterminal nodes and simply returning the minimum spanning tree on$\mathit{V}\mathbf{\text{'}}$. (Hint: Recall our approximation algorithm for the TSP.)