? A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2018, Vol. 33 Issue (4) :823-837    DOI: 10.1007/s11390-018-1858-8
Special Issue on Software Engineering for High-Confidence Systems Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem
José Alberto Fernández-Zepeda1, Daniel Brubeck-Salcedo1, Daniel Fajardo-Delgado2, Héctor Zatarain-Aceves1
1 Department of Computer Science, Center for Scientific Research and Higher Education of Ensenada Ensenada, BC 22860, Mexico;
2 Department of Systems and Computation, Instituto Technológico de Ciudad Guzmán, Guzmán, JAL 49100, Mexico

Abstract
Reference
Related Articles
Download: [PDF 1520KB]     Export: BibTeX or EndNote (RIS)  
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-BAPS for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.
Articles by authors
Keywordsbodyguard allocation problem   coalitional game   graph algorithm   Nash equilibrium     
Received 2017-04-27;
Fund:

This work was partially supported by National Council of Science and Technology (CONACyT) of Mexico under Grant No. 231224, the Program for Professional Teacher Development (PRODEP) of Mexico under Grant No. ITCGUZ-PTC-004, and the National Institute of Technology of Mexico (TecNM) under Grant No. 6307.17-P.

About author: José Alberto Fernández-Zepeda received his B.Sc. and M.Sc. degrees in electronics from the National Autonomous University of Mexico (UNAM) in 1991 and 1994, respectively, and his Ph.D. degree in computer engineering from Louisiana State University in 1999. Since 2000, he is an associate professor in the Department of Computer Science at Center for Scientific Research and Higher Education of Ensenada (CICESE), Ensenada. His research interests include analysis and design of parallel and distributed algorithms and software process improvement in small organizations.
Cite this article:   
José Alberto Fernández-Zepeda, Daniel Brubeck-Salcedo, Daniel Fajardo-Delgado, Héctor Zatarain-Aceves.A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem[J]  Journal of Computer Science and Technology, 2018,V33(4): 823-837
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-018-1858-8
Copyright 2010 by Journal of Computer Science and Technology