The sensor coverage problem is a typical combinatorial optimization problem, which is favored by researchers due to its wide practical applications. This article studies the sensor coverage problem, where each sensor has communication, sensing, and computing capabilities to collaboratively cover a certain area. First, we treat each sensor as a player, and establish a potential game for the sensor coverage problem, where the global objective is presented by the potential objective, and individual's utility is designed as a wonderful life utility. Second, we prove that under the established potential game, a Nash equilibrium can guarantee at least 50% optimality. Third, we design a synchronous game learning (SGL) distributed algorithm, where each player has a memory length$m$. Fourth, we prove that our designed SGL algorithm can guarantee that strategies of all sensors converge to a Nash equilibrium, and analyze its complexity. Finally, we demonstrate the effectiveness and superiority of our designed SGL algorithm by comparing with the existing representative optimization algorithms via numerical simulations. In addition, we also find that by employing our designed SGL algorithm, a tradeoff between solution quality and runtime could be achieved via adjusting players' memory length.

3-path vertex cover of networks is a typical optimization problem in network science, which has a wide range of applications. Toward a 3-path vertex cover of networks from distributed optimization, we first established a potential game to describe the 3-path vertex cover problem. Next, we analyze the inherent relationship between potential game and 3-path vertex cover, that is, only the solution to minimum value of potential function are minimum 3-path vertex covered solutions, and strict Nash equilibriums are intermediate solutions between minimum 3-path vertex covered solutions and 3-path vertex covered solutions. Then, we propose a bounded best response and memory-based distributed algorithm, and prove that our proposed algorithm can guarantee any initial solution converge to a strict Nash equilibrium, and further analyze the complexity of this algorithm. Finally, numerical simulations verify the effectiveness and superiority of our proposed algorithm on some representative networks and benchmark by comparing with existing representative algorithms. This work paves an effective way for distributed optimization that could be modeled as distributed potential game.

Vertex cover problem is a typical nondeterministic polynomial combinatorial optimization problem with wide applications. In order to seek a near-optimal solution in finite time, this article achieves the goal from the perspective of serial potential game optimization. Specifically, we present the vertex cover problem as a potential game, where the corresponding potential function minimizers are equivalent to the minimum vertex cover state. Then, we propose a novel polynomial-based serial game distributed algorithm, and prove that the algorithm can guarantee that strategies of all vertices converge to a$\epsilon$-minimum vertex cover ($\epsilon$-MVC) state in finite time. Compared with the existing representative optimization algorithms on networks and standard benchmarks, numerical simulations demonstrate our proposed algorithm can effectively balance solution efficiency and computation time. We hope this work provides insight for decision-makers designing a reasonable algorithm when solving nondeterministic polynomial optimization problems, so as to guarantee both solution quality and computation time.Note to Practitioners—Vertex cover problem has a wide range of practical applications. Many distributed optimization algorithms for the vertex cover problem are available in the existing literatures. However, those algorithms mainly pursue high-quality solutions in infinite time. Thus, one of the main challenges is to design a distributed algorithm that guarantees both solution quality and computation time. This article design a polynomial-based serial game algorithm, and prove that it can converge to the$\epsilon$-MVC state in finite time. This article can serve as a supplement to the existing optimization algorithms for solving the vertex cover problem.

Based on the hybrid-index model, this article investigates the asymptotic feedback set stabilization of Boolean control networks (BCNs) with random impulsive disturbances. In this model, it is assumed that the sequence of intervals between adjacent impulsive instants is independent and identically distributed. This assumption ensures that the subsequence of solutions sampled at impulsive moments is a Markov chain. Based on this assumption and the semi-tensor product (STP), random impulsive BCNs (RI-BCNs) can be converted into impulsive-interval driven probabilistic BCNs (ID-PBCNs), and the input-state transition probability matrix (IS-TPM) is constructed, the calculations of convergent target set in the hybrid domain and the time domain are discussed, and the necessary and sufficient conditions for asymptotic feedback set stabilizability are obtained. On this basis, we propose a design algorithm of state feedback controllers to stabilize RI-BCNs asymptotically with respect to a target set by using state-space partition, which enables the system to converge to a given set with the least number of impulsive intervals. Finally, the effectiveness of the obtained results is verified by simulations.

As a well-known NP-hard problem, the vertex cover problem has broad applications, which has aroused the concern of many researchers. In recent years, its related optimization problems, including the weighted vertex cover problem, the $\ell \geq 3$ path vertex cover problem, and the connected vertex cover problem, and other related optimization problems have came into the view of researchers, who have designed various optimization algorithms to solve those related optimization problems. First, based on the existing works, we give detailed descriptions of the vertex cover problem and its related optimization problems and then review the current research progress. Then, we present some main representative optimization algorithms and provide numerical results and corresponding analysis. Finally, we summarize the existing works and present the future research directions.

As a typical combinatorial optimization problem, the 3-path vertex cover problem has wide applications in practice. To solve the 3-path vertex cover problem from the perspective of distributed optimization, we treat each vertex as an agent (i.e., player) with computation, and decision-making capabilities. First, we establish a 3-player symmetric game model to describe the 3-path vertex cover problem, and design the corresponding cost function for each player. Then, we prove that under the established game model, strict Nash equilibriums (SNEs) act as the basis of the connection between 3-path vertex cover states and minimum 3-path vertex cover states. Next, we propose a novel memory-based synchronous learning (MSL) algorithm, where the initial profile strategy generation of players relies on the designed degree preference rule, and each player has a memory length for recording strategies and independently update their strategies concurrently based on the accessed local information. After that, we prove that our proposed MSL algorithm can guarantee that any strategy profile converges to an SNE, and provide a theoretical analysis of the algorithm’s complexity. Finally, we present numerous numerical simulations to demonstrate the performance of our proposed algorithm on various networks. Moreover, we find that increasing the memory length and adopting the degree preference initialization can yield a better SNE.

In this article, we investigate the asymptotical feedback set stabilization in distribution of probabilistic Boolean control networks (PBCNs). We prove that a PBCN is asymptotically feedback stabilizable to a given subset if and only if (iff) it constitutes asymptotically feedback stabilizable to the largest control-invariant subset (LCIS) contained in this subset. We proposed an algorithm to calculate the LCIS contained in any given subset with the necessary and sufficient condition for asymptotical set stabilizability in terms of obtaining the reachability matrix. In addition, we propose a method to design stabilizing feedback based on a state-space partition. Finally, the results were applied to solve asymptotical feedback output tracking and asymptotical feedback synchronization of PBCNs. Examples were detailed to demonstrate the feasibility of the proposed method and results.