The Taub Faculty of Computer Science Events and Talks

We consider flexible resource allocation problems in networks and cloud services, where the goal is to optimally utilize a limited amount of a resource (e.g., cloud servers, bandwidth, or storage capacity) available along a given time interval. Such practical scenarios give rise to variants of classic scheduling or packing problems, whose solutions lead to better performance in such criteria as throughput, revenue and resource utilization. We study the theoretical as well as practical aspects of these problems and obtain worst-case performance guarantees for the proposed algorithms. In one common scenario, a resource is utilized by a set of weighted jobs. The processing of a job consists of several contiguous stages, each having a specific length and a specific resource demand, such that the set of demands forms a decreasing sequence. As the jobs are time-critical, each is associated also with a release time and a deadline, defining the time interval in which the job can be processed. Some notable applications for this scenario include progressive download, QuickStart and prefetching methods, hierarchical image reconstruction, and routine security and maintenance tasks. The goal is to find a feasible schedule of a maximum-weight subset of the jobs. Since this problem is NP-hard already for highly restricted inputs, we focus on obtaining approximation algorithms and heuristics and present a comparative study among them. Our main result, the first constant-factor approximation algorithm for the problem, generalizes the state of art for the fundamental problem of resource constrained real-time scheduling, to scenarios where jobs may have dwindling resource requirements. Our empirical study shows that this algorithm is in fact nearly optimal for realistic inputs.