The Compact Tree Algorithm

The Compact Tree (CT) algorithm for the problem is a greedy algorithm, which like Prim's algorithm for Minimum Spanning Tree[#!clr-algorithm!#], builds a spanning tree incrementally. For each vertex $u$ in the partial spanning tree $T$ constructed so far, let $\delta(u)$ denote the length of the longest path from vertex $u$ to any other node in $T$. For each vertex $v$ that is not yet in the partial tree $T$ constructed so far, we maintain an edge $\lambda(v)=\{u,v\}$ to a vertex $u$ in the tree; $u$ is chosen to minimize $\delta(v)=c(\lambda(v))+ \delta(u)$. At each step, we select a vertex $v$ with the smallest value of $\delta(v)$ and add it and the edge $\lambda (v)$ to the tree. Then, for each vertex $v$, not yet in the tree, we update $\lambda (v)$. This process is repeated for each vertex. Figure 3.2 illustrates an example and Figure 3.3 gives a detailed description.

Figure 3.2: An Example of the Compact Tree Algorithm

[width=0.8]figure/chap3/ex-graph.eps

[width=0.8]figure/chap3/ex-1.eps

(a) A graph of 4 nodes, the numbers on the lines indicate the edge length and the numbers around the nodes indicate the degree constraints.

(b) Start with node $A$ as the root.
$\lambda(B) = \{A,B\}, \delta(B) = 1$
$\lambda(C) = \{A,C\}, \delta(C) = 5$
$\lambda(D) = \{A,D\}, \delta(D) = 3$
Add node $B$ to the tree.

[width=0.8]figure/chap3/ex-2.eps

[width=0.8]figure/chap3/ex-3.eps

(c) Node $B$ has reached its constraint, so
$\lambda(C) = \{A,C\}, \delta(C) = 6$
$\lambda(D) = \{A,D\}, \delta(D) = 4$
Add node $D$ to the tree.

(d) Update $\lambda(C) = \{C,D\}, \delta(C) = 7$

[width=0.8]figure/chap3/ex-4.eps

(e) The final tree. Note: If start with node $D$ as the root, we can construct a smaller diameter tree of length 6.

Figure 3.3: The CT Heuristic Algorithm for MDDL

The algorithm fails when it finishes with some vertices having $\delta(v) = \infty$, meaning that we cannot build a spanning tree with the specified set of degree constraints. There are two cases where this can happen: one is that a session request may arrive at a set of MSNs whose total available bandwidth (the sum of the degree constraints) is less than the minimum required degree, $2*(\vert V\vert-1)$, for a session spanning tree. In this case, the session request is simply rejected; The other case is that during the progression of the algorithm, a vertex with a degree constraint of one is added to the tree, when the sum of the spare degrees of the tree vertices is also one. Such addition leaves the newly formed tree component with zero spare degree and we cannot add any more nodes to the tree. To remedy this, we add a count of the spare degrees of the tree component and defer the addition of a leaf node if it reduces the count to zero.

We have shown that there can be no polynomial algorithm that approximates the problem to within a constant ratio. The CT algorithm, on the other hand, gives an $O(\log n)$ approximation ratio with bounded edge weights. Let $\lambda_{CT}$ and $\lambda^{*}$ denote the tree diameter constructed by the greedy CT algorithm and an optimal solution, respectively. And let $d = min(d_{max}(u))$ and $D = max(d_{max}(u))$.

Without loss of generality, let the smallest edge weight be 1 and the largest edge weight $\varepsilon$. The optimal solution can do no better than $\lambda^{*} > 2\log_{D}n$. Now, let's assume a naïve algorithm $A$ for constructing a spanning tree: at each step, $A$ adds a new node with the smallest degree constraint to an existing node in the tree whose degree constraint has not been met. By keep adding nodes to an existing node as long as its degree constraint allows, it results in a tree height of at most $\log_d n$. In the worst case, each selected edge has weight of $\varepsilon$, so $\lambda_{A} < 2\varepsilon(\log_{d}n)$. We observe that $\lambda_{CT} \leq \lambda_{A}$. Because if all intermediate nodes in tree $T$ constructed by the CT algorithm are at their degree constraints, then $\lambda_{CT}$ cannot be worse than $\lambda_A$; If there is an intermediate node $X$ in $T$ that has not met its degree constraint, then moving one of the leaf node that resides on the longest path in $T$ to $X$ would increase the diameter of $T$. Therefore, $\lambda_{CT} < k\lambda^{*}$, where $k = \varepsilon\log_{d} D$.