The Taub Faculty of Computer Science Events and Talks

Resource allocation problems arise in a wide range of applications. In many of these classic problems, we are given a set of requests competing for resources, where each request utilizes predefined amounts of the resources. We seek a feasible allocation of the resources, subject to availability constraints, so as to maximize (or, minimize) certain objective function. However, in recent applications, such as flex-grid all-optical networks, cloud computing, and cellular networks, resource requests may be partially satisfied, and the amounts of allocated resources come into play in the objective function. These scenarios motivate the study of flexible variants of classic resource allocation problems. In this talk, I will present our results for such flexible resource allocation problems, where each request can be allocated an amount of the resource within a specified range, with some profit accrued from each allocated resource unit. The goal is to feasibly assign the available resources, such that the total profit is maximized. This includes, among others, flexible variants of the well known Bandwidth Allocation and Storage Allocation problems, as well as Flexible Scheduling on Related Machines with Assignment Restrictions.