Layered Multicast Scheduling
We present a simple 2-approximation randomized algorithm for the layered multicast scheduling problem. In the presence of user subscription profiles (the L1 objective), we provide a deterministic 2-approximation algorithm for the general multilayer cases. If the user subscription profiles are absent (the L? objective), we present a combinatorial construction for the two-layer case which is 1.6875-approximation ignoring an additive constant. Further, we provide a polynomial-time approximation algorithm that uses a fundamentally different approach and can address the general layered multicast scheduling problem with an arbitrary number of layers. This algorithm is 1.334-approximation for the two-layer case and 1.862-approximation for the general multi-layer cases.
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:network apporximation algorithm layered multicast scheduling
Date of Publication:01/01/2008