ALCOMFT-TR-01-47

Stefano Leonardi, Alberto Marchetti-Spaccamela and andrea Vitaletti
Approximation algorithms for bandwidth and storage allocation under real time constraints
Rome. Work package 2. April 2001.

Abstract: \beginabstract 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. [STOC00]. The techniques we use are different from those of Bar-Noy et al. and allows to obtain better approximation ratio. \endabstract

Postscript file: ALCOMFT-TR-01-47.ps.gz (110 kb).