Institute of Electrical & Electronic Engineers
In this paper, the authors consider the problem of assigning a set of clients with demands to a set of servers with capacities and degree constraints. The goal is to find an allocation such that the number of clients assigned to a server is smaller than the server's degree and their overall demand is smaller than the server's capacity, while maximizing the overall throughput. This problem has several natural applications in the context of independent tasks scheduling or virtual machines allocation. They consider both the offline (when clients are known beforehand) and the online (when clients can join and leave the system at any time) versions of the problem.