Back to Search
Start Over
A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem.
- Source :
- Journal of Computer Science & Technology (10009000); Jul2018, Vol. 33 Issue 4, p823-837, 15p
- Publication Year :
- 2018
-
Abstract
- We address the bodyguard allocation problem (BAP), an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAP<subscript>S</subscript> for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10009000
- Volume :
- 33
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Journal of Computer Science & Technology (10009000)
- Publication Type :
- Academic Journal
- Accession number :
- 130695013
- Full Text :
- https://doi.org/10.1007/s11390-018-1858-8