Allocating servers in infostations for bounded simultaneous requests ?
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 hc 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 hc 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{hc} h = min { h c } . Generalizations of the problem are considered, where each request r  is also characterized by a bandwidth rate wr 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, multiprocessor task scheduling, and interval graph coloring as special cases, and they admit on-line algorithms providing constant approximations.
infostations server allocation on-line algorithms bin-packing greedy algorithms approximation algorithms interval coloring