Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints

Stefano Leonardi, Alberto Marchetti-Spaccamela, Andrea Vitaletti

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


The problem we consider is motivated by allocating bandwidth slots to communication requests on a satellite channel under real time constraints. Accepted requests must be scheduled on non-intersecting rectangles in the time/bandwidth Cartesian space with the goal of maximizing the benefit obtained from accepted requests. This problem turns out to be equal to the maximization version of the well known Dynamic Storage Allocation problem when storage size is limited and requests must be accommodated within a prescribed time interval. We present constant approximation algorithms for the problem introduced in this paper using as a basic step the solution of a fractional Linear Programming formulation. We also show the extension to the case in which multiple channels are available for accepting communication requests. This problem has been independently studied by Bar-Noy et al \cite{BBFNS00}. The techniques we use are different from those of \cite{BBFNS00} and allows to obtain better approximation ratio.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems