IIIT Hyderabad Publications |
|||||||||
|
Fast Algorithms for Optimal Coalition Formation in Federated CloudsAuthors: Yash Khandelwal,Suresh Purini,Viswanath Puduru Puduru Conference: International conference on Utility and cloud computing Date: 2016-12-06 Report no: IIIT/TR/2016/43 AbstractIn 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. |