Brief announcement: Approximation algorithms for preemptive resource allocation

Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Cloud services require the allocation of scarce resources to multiple user requests (jobs) in a setting that facilitates preemption and migration, while respecting resource and timing constraints. This gives rise to the following variants of the classical resource allocation problem (RAP). The input is a set J of jobs and a set M of homogeneous hosts, each has available amount of some resource. A job is associated with a release time, a due date, a weight and a given length, as well as its resource requirement. A feasible schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. We consider two essential objectives: throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M, and resource minimization (MinR), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We address these fundamental problems, which have been studied previously in the non-preemptive model, and develop novel techniques for tackling them. In the full version of the paper, we present an Ω(1)-approximation algorithm for MaxT, assuming there is sufficient slack for each job to be completed in its time window. For MinR we study a more general setting with d resources and derive an O(log d)-approximation for any fixed d ≥ 1, under the assumption that time windows are not too small. This assumption can be removed leading to a slightly worse ratio of O(log d log T), where T is the maximum due date of any job.

Original languageEnglish (US)
Title of host publicationSPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Number of pages3
ISBN (Electronic)9781450357999
StatePublished - Jul 11 2018
Externally publishedYes
Event30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 - Vienna, Austria
Duration: Jul 16 2018Jul 18 2018

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures


Conference30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


  • Approximation algorithms
  • Preemptive resource allocation
  • Real-time scheduling
  • Resource minimization
  • Throughput maximization


Dive into the research topics of 'Brief announcement: Approximation algorithms for preemptive resource allocation'. Together they form a unique fingerprint.

Cite this