A GPU-Based Tabu Search Algorithm for Large Instances of the Generalized Max-Mean Dispersion Problem

The Generalized Max-Mean Dispersion Problem (GMaxMeanDP) is important in areas such as web page classification, community mining, and social network analysis. However, current methods for this problem face challenges with large-scale instances, primarily due to memory inefficiencies in their matrix-based representations and the escalating computational time required to execute these methods. This study proposes a parallel tabu search algorithm using GPUs to accelerate local search and optimized data structures to reduce memory overhead. Tests on instances with 2,000 to 20,000 vertices show that the algorithm outperforms existing methods in the literature in terms of solution quality and execution time, making it an effective and scalable solution for large-scale scenarios.