## 1 Introduction
### Problem Description and Existing Work  
In technical terms, the MPIDS problem can be described as follows. Given a simple, connected undirected graph \(G=(V,E)\) it requires to find a dominating set of minimum cardinality such that at least half of the neighbors of each vertex form part of the dominating set. However, the problem was shown to be APX-hard [13]. Note that a problem is said to be APX-hard if there is a polynomial time reduction scheme from every problem in APX to that problem. Moreover, if a problem is APX-hard, it is also NP-hard. Therefore, most of the past and current research efforts concerning the MPIDS problem are focused on greedy heuristics and on some evolutionary approaches. Greedy heuristics [14] are procedures that generate a solution step by step, making a locally optimal choice at each stage based on a so-called greedy function. We briefly review the existing approaches in the following. The first greedy algorithm for the MPIDS problem, referred to as [PERSON]'s greedy algorithm [13], is a \(H(\Delta)\)-approximation algorithm with \(O(n^{3})\) time complexity, where \(n=|V|\), \(\Delta\) is the maximum vertex degree, and \(H\) is the harmonic function. Another greedy algorithm, referred to as [PERSON]'s greedy, was published in [15]. This algorithm requires \(O(n^{2})\) time. It differs from the previous one in the way in which the next vertex at each construction step is chosen. That is, they differ with respect to the used greedy function. An improved version of [PERSON]'s greedy, referred to as [PERSON]'s greedy, was proposed in [16]. It incorporates a tie-breaking strategy based on [PERSON]'s greedy. More recently, [PERSON] et al. [17] presented a fast greedy heuristic with a complexity of \(O(n\lg n+m)\) that outperforms all previous greedy approaches both in terms of solution quality and computational time. Therefore, [PERSON]'s greedy is considered as the currently best-performing greedy algorithm for the MPIDS problem.  
To the best of our knowledge, there are only two studies that have attempted to solve the MPIDS problem using metaheuristic approaches. Metaheuristics are approximate techniques for solving hard optimization problems of different types. They are among the most popular algorithms in the context of problem instances that are too large (or too complex) to be solved by exact techniques. Many metaheuristics are built upon subordinate algorithmic components such as greedy heuristics and local search algorithms. Examples of such metaheuristics include simulated annealing, tabu search, iterated local search, and greedy randomized adaptive search procedures. However, the family of metaheuristics also includes a whole range of bio-inspired techniques such as ant colony optimization, genetic and evolutionary algorithms, and particle swarm optimization. Especially in combinatorial optimization, metaheuristics have had considerable success in application areas such as scheduling, routing, bioinformatics, medical research, passenger and freight terminal operations, and data classification. We refer the interested reader to [18; 19] for further information. The MPIDS problem was first tackled by a memetic algorithm [20], called ILPMA, which uses tabu search for improving solutions. The second one is a hybrid approach, referred to as HSIA, that combines a genetic algorithm with particle swarm optimization. Both ILPMA and HSIA share two common features: they incorporate a greedy randomized adaptive algorithm similar to GRASP [21] to seed the initial population with good solutions and their performances are compared with those of the greedy algorithms.