IIIT Hyderabad Publications
Fast Algorithms for Optimal Coalition Formation in Federated Clouds
Authors: Yash Khandelwal,Suresh Purini,Viswanath Puduru Puduru
Conference: International conference on Utility and cloud computing
Report no: IIIT/TR/2016/43
In this paper, we formulate the optimal coalition formation in federated clouds as an integer linear programming prob- lem under the cloud service brokerage model proposed by Mashayekhy et al. Then we propose a fast polynomial time greedy algorithm to find a near optimal coalition. The profit generated by the federation obtained using the greedy algorithm is within a negligible 0.06 percent of the optimal on an average. The greedy algorithm finds a federation 200 times faster on an average when compared with the Merge- Split algorithm. The payoff distribution within a federation is determined using exact Banzhaf index computation whereas the Merge-Split algorithm arrives at a payoff using an estimate of Banzhaf values. By computing the payoff distribution after the federation formation, we are able to achieve 66x speedup when compared with the Merge-Split algorithm.
Full paper: pdf
Centre for Software Engineering Research Lab
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved.