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

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

作者机构：the Adaptive Networks and Control LaboratoryDepartment of Electronic EngineeringFudan UniversityShanghai 200433China the College of Mathematics and Computer ScienceZhejiang Normal UniversityJinhua 321004 Yuxi Middle SchoolTaizhou 317399China IEEE the College of Physics and Electronics Information EngineeringZhejiang Normal UniversityJinhua 321004China the College of Mathematics and Computer ScienceZhejiang Normal UniversityJinhua 321004China the Adaptive Networks and Control LaboratoryDepartment of Electronic EngineeringFudan UniversityShanghai 200433 the Institute of Complex Networks and Intelligent SystemsShanghai Research Institute for Intelligent Autonomous SystemsTongji UniversityShanghai 201210China 

出 版 物：《IEEE/CAA Journal of Automatica Sinica》 (自动化学报（英文版）)

年 卷 期：2023年第10卷第2期

页      面：512-523页

核心收录：

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

基　　金：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 

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

摘      要：Weighted vertex cover(WVC)is one of the most important combinatorial optimization *** this paper,we provide a new game optimization to achieve efficiency and time of solutions for the WVC problem of weighted *** first model the WVC problem as a general game on weighted *** the framework of a game,we newly define several cover states to describe the WVC ***,we reveal the relationship among these cover states of the weighted network and the strict Nash equilibriums(SNEs)of the ***,we propose a game-based asynchronous algorithm(GAA),which can theoretically guarantee that all cover states of vertices converging in an SNE with polynomial ***,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 ***,numerical simulations demonstrate that the proposed IGAA can obtain a better approximate solution in promising computation time compared with the existing representative algorithms.