PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bertossi A. A., Pinotti M. C., Rizzi R., Gupta P. Allocating Servers in Infostations for Bounded Simultaneous Requests. In: Journal of Parallel and Distributed Computing, vol. 64 (10) pp. 1113 - 1126. Elsevier, 2004.
 
 
Abstract
(English)
The Server Allocation with Bounded Simultaneous Requests problem arises in isolated infostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterized by a temporal interval and a category, an integer $k$, and an integer $h_c$ for each category $c$, the problem consists in assigning a server to each request in such a way that at most $k$ mutually simultaneous requests are assigned to the same server at the same time, out of which at most $h_c$ are of category $c$, and the minimum number of servers is used. Since this problem is computationally intractable, a $2$-approximation on-line algorithm is exhibited which asymptotically gives a $left(2-frac{h}{k}right)$-approximation, where $h = min {h_c}$. Generalizations of the problem are considered, where each request $r$ is also characterized by a bandwidth rate $w_r$, and the sum of the bandwidth rates of the simultaneous requests assigned to the same server at the same time is bounded, and whereeach request is characterized also by a gender bandwidth. Such generalizations contain Bin-Packing, Multiprocessor Task Scheduling, and Interval Graph Coloring as special cases, and they admit on-line algorithms providing constant approximations.
URL: http://www.jpdc.org
Subject Infostations
Greedy algorithms
C.2 Computer.Communication Networks


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional