On the complexity of the bandwidth management problem for scalable coding video streaming on a public-shared network

This paper proposes a novel concept of using the sharable bandwidth of public-shared network, like FON network, to construct an efficient video delivery system. We show that the problem of constructing an architecture to serve the video streaming requests by using a minimum amount of sharable bandwidth is NP-Hard. A linear approximation algorithm is also proposed to manage the public-shared bandwidth so that all clients are served and the total amount of employed sharable bandwidth is no greater than twice of the optimal solution.