Lower bound for multimedia multicast routing

The optimal multimedia multicast routing problem is to determine a multicast tree of minimal cost to connect a given source node to a given set of destination nodes while fulfilling the delay requirement for multimedia information. This problem has been shown to be NP-complete (Kompella et al., 1993), and hence fast and good heuristic algorithms must be used in practice for a reasonable network size. The authors derive a lower bound on the cost of the optimal multicast trees by Lagrangean relaxation and problem decomposition. The numerical results for some standard test problems demonstrate that the lower bound is very tight and differs from the optimal solutions by only a few percent on average. In addition, the lower bound can be computed quite quickly and the computation time on a SUN workstation is only a few minutes for the networks with 100 nodes. This tight lower bound can be used to evaluate whether any given heuristic algorithm for multimedia multicast routing is close-to-optimal.