A Lagrangean Relaxation and Decomposition Algorithm for the Video Placement and Routing Problem

Tolga Bektas (tolgabbilkent.edu.tr)
Osman Oguz (ooguzbilkent.edu.tr)
Iradj Ouveysi (iradjouveysiyahoo.co.uk)

Abstract: 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.

Keywords: Video-on-Demand, Placement, Routing, Integer Programming, Lagrangean Relaxation, Decomposition.

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Citation: Technical Report, Bilkent University, March 2005

Download: [Postscript][PDF]

Entry Submitted: 05/02/2005
Entry Accepted: 05/02/2005
Entry Last Modified: 05/02/2005

Modify/Update this entry