A simple and effective algorithm for the maximum happy vertices problem

In a recent paper, a solution approach to the Maximum Happy Vertices Problem has been proposed. The approach is based on a constructive heuristic improved by a matheuristic local search phase. We propose a new procedure able to outperform the previous solution algorithm both in terms of solution quality and computational time. Our approach is based on simple ingredients implying as starting solution generator an approximation algorithm and as an improving phase a new matheuristic local search. The procedure is then extended to a multi-start configuration, able to further improve the solution quality at the cost of an acceptable increase in computational time.