Approximation algorithms for the restricted steiner tree problem

Emerging group applications require efficient multicast schemes that provide Quality of Service (QoS) guar - Antees. QoS can be achieved by provisioning multicast trees that satisfy QoS constraints. Since the efficient usage of network re-sources is an important requirement, the cost of the constructed multicast trees should be as small as possiblE. Accordingly, in this paper we investigate the fundamental problem of finding a multicast tree that satisfies end-to-end QoS constraints at minimum cost. We focus on additive QoS constraints such as delay or jitteR. This problem, referred to as the Restricted Steiner Tree prob-lem, has been extensively studied. However, existing solutions have either relied on heuristic approaches or considered special cases, such as the case where the delay and cost of each edge are identical. Moreover, many of the heuristic approaches are based on restricting assumptions, such as symmetric edge delays. In this study we present an approximate algorithm that achieves, for any fixed i > 1 and > 0, an approximation ratio of 2(1+)i³K^1/i, where K is the number of terminals. Moreover, by using our methods we can obtain an approximate solution to this problem out of any given approximate algorithm of Its (simpler) unconstrained directed version, with about identical (e-close) performance guarantees.

Approximation algorithms for the restricted steiner tree problem Conference Paper