Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game  

作　　者：Jie Chen Kaiyi Luo Changbing Tang Zhao Zhang Xiang Li 

机构地区：[1]the Adaptive Networks and Control Laboratory,Department of Electronic Engineering,Fudan University,Shanghai 200433,China [2]the College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004 [3]Yuxi Middle School,Taizhou 317399,China [4]IEEE [5]the College of Physics and Electronics Information Engineering,Zhejiang Normal University,Jinhua 321004,China [6]the College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004,China [7]the Adaptive Networks and Control Laboratory,Department of Electronic Engineering,Fudan University,Shanghai 200433 [8]the Institute of Complex Networks and Intelligent Systems,Shanghai Research Institute for Intelligent Autonomous Systems,Tongji University,Shanghai 201210,China

出　　处：《IEEE/CAA Journal of Automatica Sinica》2023年第2期512-523,共12页自动化学报（英文版）

基　　金：partly supported by the National Natural Science Foundation of China(61751303,U20A2068,11771013);the Zhejiang Provincial Natural Science Foundation of China(LD19A010001);the Fundamental Research Funds for the Central Universities。

摘　　要：Weighted vertex cover(WVC)is one of the most important combinatorial optimization problems.In this paper,we provide a new game optimization to achieve efficiency and time of solutions for the WVC problem of weighted networks.We first model the WVC problem as a general game on weighted networks.Under the framework of a game,we newly define several cover states to describe the WVC problem.Moreover,we reveal the relationship among these cover states of the weighted network and the strict Nash equilibriums(SNEs)of the game.Then,we propose a game-based asynchronous algorithm(GAA),which can theoretically guarantee that all cover states of vertices converging in an SNE with polynomial time.Subsequently,we improve the GAA by adding 2-hop and 3-hop adjustment mechanisms,termed the improved game-based asynchronous algorithm(IGAA),in which we prove that it can obtain a better solution to the WVC problem than using a the GAA.Finally,numerical simulations demonstrate that the proposed IGAA can obtain a better approximate solution in promising computation time compared with the existing representative algorithms.

关 键 词：Game-based asynchronous algorithm(GAA) game optimization polynomial time strict Nash equilibrium(SNE) weighted vertex cover(WVC) 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]