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 thatat most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most hc 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 - \frac{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 wr, 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.