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

• William Rosendo UFAL
• Ermeson Andrade UFRPE
• Bruno Nogueira UFAL

DOI: https://doi.org/10.5753/semish.2025.9110

Abstract

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.

References

Carrasco, R. et al. (2015). Tabu search for the max-mean dispersion problem. Knowledge Based System, 85:256–264.

Essaid, M., Idoumghar, L., Lepagnot, J., and Brevilliers, M. (2019). Gpu parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emergent and Distributed Systems, 34(5):497–522.

Glover, F. W. and Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers, Dordrecht.

Kerchove, C. and Dooren, P. V. (2008). The page trust algorithm: How to rank web pages when negative links are allowed? pages 346–352.

Lai, X., Hao, J.-K., and Glover, F. (2020). A study of two evolutionary/tabu search approaches for the generalized max-mean dispersion problem. Expert Systems with Applications, 139:112856.

Nogueira, B., Rosendo, W., Tavares, E., and Andrade, E. (2024). Gpu tabu search: a study on using gpu to solve massive instances of the maximum diversity problem. Journal of Parallel and Distributed Computing, page 105012.

Nosferalatu (2020). A simple gpu hash table. [link].

Prokopyev, O. A., Kong, N., and Martinez-Torres, D. L. (2009). The equitable dispersion problem. European Journal of Operational Research, 197(1):59–67.

Wilt, N. (2013). The CUDA Handbook: A Comprehensive Guide to GPU Programming. Pearson Education.

Yang, B., Cheung, W., and Liu, J. (2007). Community mining from signed social networks. IEEE Transactions on Knowledge & Data Engineering, 19(10):1333–1348.

Zhao, J., Hifi, M., and Latrem, K. (2024). Hybrid particle swarm optimization and skewed variable neighborhood search techniques for the generalized max-mean dispersion problem.

Zhou, Y., Hao, J.-K., and Duval, B. (2017). Opposition-based memetic search for the maximum diversity problem. IEEE Transactions on Evolutionary Computation, 21(5):731–745.