Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game
文献类型：期刊论文
| 作者 | Jie Chen; Kaiyi Luo; Changbing Tang; Zhao Zhang; Xiang Li
|
| 刊名 | IEEE/CAA Journal of Automatica Sinica
 |
| 出版日期 | 2023 |
| 卷号 | 10期号:2页码:512-523 |
| 关键词 | |
| ISSN号 | 2329-9266 |
| DOI | 10.1109/JAS.2022.105521 |
| 英文摘要 | 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. |
| 源URL | [http://ir.ia.ac.cn/handle/173211/50863]  |
| 专题 | 自动化研究所_学术期刊_IEEE/CAA Journal of Automatica Sinica |
| 推荐引用方式 GB/T 7714 | Jie Chen,Kaiyi Luo,Changbing Tang,et al. Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game[J]. IEEE/CAA Journal of Automatica Sinica,2023,10(2):512-523. |
| APA | Jie Chen,Kaiyi Luo,Changbing Tang,Zhao Zhang,&Xiang Li.(2023).Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game.IEEE/CAA Journal of Automatica Sinica,10(2),512-523. |
| MLA | Jie Chen,et al."Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game".IEEE/CAA Journal of Automatica Sinica 10.2(2023):512-523. |
入库方式： OAI收割
来源：自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。