We use cookies to improve your experience with our site.
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, 33(4): 823-837. DOI: 10.1007/s11390-018-1858-8
Citation: 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, 33(4): 823-837. DOI: 10.1007/s11390-018-1858-8

A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem

  • 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.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return