Title:
Online Algorithms for Maximal Dense Trees and Selective Multicast
Author:
- 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).