Simple Heuristics for the Rooted Max Tree Coverage Problem

The Max Tree Coverage (MTC) problem is the dual of the classic k-MST problem and has wide applications in areas such as network design and vehicle routing. Given a graph G with nonnegative costs defined on edges, a vertex \(r \in V(G)\) , and a budget B, the rooted Max Tree Coverage problem asks to find a tree rooted at r having total cost at most B, so that the number of vertices included in the tree is maximized. This problem is NP-hard and has constant factor approximation algorithms. However, the existing approximation algorithms for rooted MTC is very complicated and hard to be implemented practically. In this paper, we develop a simple CMSA heuristic for rooted MTC for the first time, where CMSA (Construct, Merge, Solve and Adapt) is a meta-heuristic proposed recently. We also formulate a polynomial size mixed integer linear program for rooted MTC for the first time. Experimental results show that CMSA has very good practical performance. For the small size instances of the problem, CMSA almost finds the optimal solutions. For the large size instances, CMSA finds solutions better than that of CPLEX within the same running time and two additional greedy algorithms. Note that within an admissible running time limit, CPLEX returns the best solutions ever found (not guarantee to be optimal).