Allocating Servers in Infostations for Bounded Simultaneous Requests

The Server Allocation with Bounded Simultaneous Requests problem arises in 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 where each request is characterized also by a gender bandwidth. Such generalizations contain Bin-Packing and Multiprocessor Task Scheduling as special cases, and they admit on-line algorithms providing constant approximations.