Technical Report PHD-2017-07

Title: Flexible Resource Allocation for Network Problems
Authors: Ariella Voloshin
Supervisors: Shmuel Zaks and Hadas Shachnai
PDFCurrently accessibly only within the Technion network
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2017
To the main CS technical reports page

Computer science department, Technion