This paper is concerned with the maximum general budgeted dominating set problem (MaxGBDS), which is a newly defined variant of the minimum dominating set problem. Given a graph \(G = (V, E)\) , with V as the vertex set and E as the edge set, a vertex \(v \in V\) is considered to be dominated by a set \(S \subseteq V\) if either \(v \in S\) or it has at least one neighbor in S. MaxGBDS problem can be defined as follows: for a profit function \(p: V \rightarrow \mathbb {R}^+\) on the vertex set V and a budget threshold B, determine a set \(D \subseteq V\) with at most B vertices such that the total profit of the vertices dominated by D is maximized. In some real world scenarios, there is a budget constraint on dominating set cardinality |D|, and full domination of the graph is not required. In such situations, MaxGBDS is useful. Practical utility of MaxGBDS extends to a variety of fields, such as facility location, designing efficient networks, analyzing social networks, and managing resource distribution. So far no metaheuristic approach has been proposed for MaxGBDS. In this work, we present two metaheuristic approaches for MaxGBDS, namely a genetic algorithm, and an artificial bee colony algorithm. Various components of our approaches have been designed taking into account the characteristics of MaxGBDS. After being extensively tested on general, unit disk and real-world graphs, our approaches have been found to be effective.
