Randomized approximation scheme for resource allocation in hybrid-cloud environment

Mohammad Reza HoseinyFarahabady*, Young Choon Lee, Albert Y. Zomaya

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


Using the virtually unlimited resource capacity of public cloud, dynamic scaling out of large-scale applications is facilitated. A critical question arises practically here is how to run such applications effectively in terms of both cost and performance. In this paper, we explore how resources in the hybrid-cloud environment should be used to run Bag-of-Tasks applications. Having introduced a simple yet effective objective function, our algorithm helps the user to make a better decision for realization of his/her goal. Then, we cope with the problem in two different cases of “known” and “unknown” running time of available tasks. A solution to approximate the optimal value of user’s objective function will be provided for each case. Specifically, a fully polynomial-time randomized approximation scheme based on a Monte Carlo sampling method will be presented in case of unknown running time. The experimental results confirm that our algorithm approximates the optimal solution with a little scheduling overhead.

Original languageEnglish
Pages (from-to)576-592
Number of pages17
JournalJournal of Supercomputing
Issue number2
Publication statusPublished - 1 Aug 2014
Externally publishedYes


  • Bag-of-Tasks applications
  • Cloud resource allocation
  • Divisible load theory (DLT)
  • Monte Carlo sampling
  • Optimality criterion
  • Randomized approximation scheme


Dive into the research topics of 'Randomized approximation scheme for resource allocation in hybrid-cloud environment'. Together they form a unique fingerprint.

Cite this