Cloudy Knapsack Problems: an Optimization Model for Distributed Cloud-assisted Systems

Cloud-assisted approaches for both peer-to-peer systems and mobile apps require optimized use of elastic cloud resources. Due to budget constraints, a subset of the tasks has to be selected for offloading considering context parameters like device battery level and task variability. This leads to the challenging problem of context-sensitive task scheduling on elastic resources with a limited global view, which is not addressed by existing works. We identify a new class of formal problems called cloudy knapsack problems to effectively model the same. Abstracting out the problem formally can spur future independent works related to different variants of the problem and corresponding bounds and optimal algorithms. We illustrate the global view related issues through simulations, identify some theoretical bounds for a variant of cloudy knapsack problems and discuss several open problems.