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 |

1) Download Document PDF |

Open access Restricted Private