Online Algorithms for Maximal Dense Trees and Selective Multicast


Baruch Awerbuch
Affiliation: Johns Hopkins University
Abstract: Online Selective Multicast is defined as follows. Various network users issue online requests for a connection to a certain multicast source. The network either connects this request or rejects it. If request is connected, a path is established starting at the requesting user and ending either at the source or at one of the users previously connected to the same source. The goal is to maximize total number of users connected subject to network capacity constraints, namely, that number of connections to different sources passing thru any edge does not exceed the capacity of that edge. Generalizations of this problem include setting the pricing policy in order to maximize total network revenues, or optimizing network design and synthesis.

The above problem has not been previously defined or analyzed in the literature. We survey the following special cases, and outline a way to generalize them:

--Non-selective Batch Arrival multicast: This is the Admission/Route Selection problem for regular routing studied by Awerbuch, Azar and Plotkin (FOCS 93).

--Selective Batch arrival Multicast: This is the offline version on Maximal Dense tree which is closely related to k-MST problem studied by Awerbuch, Azar, Blum and Vempala (STOC 95).

--Link topology: This is effectively the Winner Picking problem studied by Awerbuch, Azar, Fiat and Leighton (STOC96).

--General topology, non-interleaved arrival: This is the Cable Wire problem, recently studied by Awerbuch and Singh (1996).