Aplicação do Golden Ball para o Problema do Corte Máximo - Silva, Jailon W. B. Oliveira da; Araújo, Carlos V. Dantas; Soares, Pablo L. Braga (Anais do Encontro de Teoria da Computação (ETC), 2025)
Este trabalho aplica a meta-heurística Golden Ball ao Problema do Corte Máximo em grafos, modelando soluções como jogadores organizados em times que evoluem, visando identificar partições dos vértices que maximizem a soma dos pesos das arestas cortadas. Foram avaliadas 120 instâncias da Biq Mac Library, e os experimentos mostraram que o Golden Ball gera soluções satisfatórias, com desvio médio de 37% no conjunto Be em 10 segundos e apenas 1.4% em 1200 segundos. Como método evolutivo, seus resultados melhoram com mais tempo de execução. A abordagem foi comparada ao solver Biq Mac Library, referência na área, que operou por até 10800 segundos.