Video on Demand (VoD) is a technology used to provide a number of programs to a number of users on request. In developing a VoD system, a fundamental problem is load balancing, which is further characterized by optimally placing videos to a number of predefined servers and routing the user program requests to available resources. In this paper, we develop an exact solution algorithm based on Lagrangean relaxation and decomposition to solve a previously proposed integer programming formulation of the problem. The novelty of the approach can be described as the use of integer programs to obtain feasible solutions to the problem. We also provide a modification to accelerate the proposed algorithm. Computational results indicate that for randomly generated and reasonable sized instances, the algorithms are capable of producing good quality solutions in a short amount of time.
Citation
Technical Report, Bilkent University, March 2005