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

doi:10.1109/JAS.2022.105521

CASIA OpenIR > 学术期刊 > IEEE/CAA Journal of Automatica Sinica

	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
ISSN	2329-9266
	2023
卷号	10 期号:2 页码:512-523
摘要	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)
DOI	10.1109/JAS.2022.105521
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	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.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
JAS-2021-0884.pdf（6320KB）	期刊论文	出版稿	开放获取	CC BY-NC-SA	浏览下载