Allocating servers in infostations for on-demand communications

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 Server Allocation with Bounded Simultaneous Requests 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 (2 $h/k)-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 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.