Optimization Research Of Weighted Vertex Cover Based On Game Theory

With the continuous development of science and technology,networks are becoming more and more popular around the world.For example,people use sensor networks to monitor urban traffic,detect intruders,maintain equipment,etc.Such applications can be modeled as minimum weighted vertex cover problems.The minimum weighted vertex cover problem is a classic combinatorial optimization problem that already has good centralized approximation algorithms.However,currently,because the network is large scale and highly dynamic,self-organizing distributed algorithms are more preferable.This thesis studies the minimum weighted(connected)vertex cover problem using game theory,and designs corresponding distributed algorithms.The treatment of heterogeneous weight is the key of this study.To begin with,this paper will study the modeling and game optimization of the minimum weighted vertex cover problem.First,this thesis constructs an asymmetric game model and proves that any Nash equilibrium on this model corresponds to the locally minimum weighted vertex cover set.Second,a distributed game algorithm Game-based Asynchronous algorithm(GAA)is designed and is updated asynchronously.This algorithm can ensure that a Nash equilibrium on the model is reached within finite running time.In particular,the running time on a homogeneous network is O(n2),where n is the number of vertices.Third,we design an Improved Game-based Asynchronous algorithm(IGAA)that is being updated asynchronous and has some local adjustment in order to further improve the solution obtained by GAA.Fourth,the performance of IGAA is verified through numerical simulation.Compared with other game algorithms,IGAA has significant advantages in time and stability.Then,this paper will examine the game optimization of the minimum weighted vertex cover problem with connectivity conditions.First,a distributed algorithm Con-nectivity Judgment algorithm(CJA)is designed to improve connectivity.Based on CJA and IGAA,we design a distributed game algorithm Asynchronous Connection-based al-gorithm(ACA)to ensure that a minimum weighted connected vertex cover is obtained within finite running time,and in particular,the running time on a homogeneous net-work is O(n4).Second,the performance of ACA is verified through numerical simulation.Compared with the greedy algorithm,ACA has higher accuracy.