Ph.D Thesis

Ph.D StudentVoloshin Ariella
SubjectFlexible Resource Allocation for Network Problems
DepartmentDepartment of Computer Science
Supervisors PROFESSOR EMERITUS Shmuel Zaks
PROF. Hadas Shachnai
Full Thesis textFull thesis text - English Version


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 elastic optical networks, cloud computing and cellular networks, resource requests may be partially satisfied, as long as a minimal amount of resources is provided. The allocated amount of resource for the activities actually determines its performance, quality of service, or processing time. 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.

We consider 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 flexible variants of the well known Bandwidth Allocation and Storage Allocation problems, where each request consists of a minimum and a maximum resource requirement for the duration of its execution, a flexible variant of Dynamic Storage Allocation, and the problem of Flexible Scheduling on Related Machines with Assignment Restrictions.

While all of the problems are NP-hard, we give proofs of hardness already for highly restricted instances. Our main results are constant factor approximation algorithms, which couple LP-based with combinatorial techniques in solving our problems. We further show the usefulness of resource augmentation in tackling these problems. Finally, applying our techniques, we obtain an algorithm that improves the best known approximation ratio for the classical Storage Allocation problem.