Distributed Optimization for Weighted Vertex Cover via Heuristic Game Theoretic Learning
Changhao Sun, Xiaochu Wang, Huaxin Qiu, Qián Chen, Qingrui Zhou · 2020
For the generation of higher-quality solutions to the distributed minimum weighted vertex cover (MWVC) problem, we propose a game theoretic learning algorithm by designing a weighted memory based rule. Being viewed as a rational player, each node in the network stochastically updates its action by following a probability distribution that is determined by neighborhood information including node degrees and weights. Within the framework of game theory, we prove that our method converges with probability 1 to Nash equilibria that correspond to near-optimal vertex cover solutions. Moreover, simulation results show that the memory length provides an additional freedom for solution efficiency improvement such that better system level objectives are more likely to be obtained by using a longer memory length. Comparison experiments with typical distributed algorithms demonstrate the superiority of the presented methodology to the state of the art.