A GPU-Based Tabu Search Algorithm for Large Instances of the Generalized Max-Mean Dispersion Problem - Rosendo, William; Andrade, Ermeson; Nogueira, Bruno (Anais do Seminário Integrado de Software e Hardware (SEMISH); 2025: Anais do LII Seminário Integrado de Software e HardwareDO - 10.5753/semish.2025.9110, 2025)
O Problema de Dispersão Máxima Média Ponderada (GMaxMeanDP) é importante em áreas como classificação de páginas web, mineração de comunidades e análise de redes sociais. No entanto, os métodos atuais para esse problema enfrentam desafios em instâncias de grande escala, principalmente devido a ineficiências de memória em suas representações matriciais e ao crescente tempo computacional necessário para executá-los. Este estudo propõe um algoritmo de busca tabu paralelizado, utilizando GPUs para acelerar a busca local e estruturas de dados otimizadas para reduzir a sobrecarga de memória. Testes em instâncias de 2.000 a 20.000 vértices mostram que o algoritmo supera os métodos existentes na literatura em termos de qualidade das soluções e tempo de execução, sendo uma solução eficaz e escalável para cenários massivos.