Busca Local Acelerada por Aprendizado de Máquina e Análise Espectral para o Problema do Corte Máximo

Resumo

Este trabalho apresenta uma metodologia híbrida para o Problema do Corte Máximo (Max-Cut), combinando teoria espectral de grafos com busca local acelerada por aprendizado de máquina. A abordagem proposta gera soluções iniciais de alta qualidade através de análise espectral e emprega um modelo de regressão leve para guiar a exploração da vizinhança, reduzindo drasticamente o tempo computacional enquanto mantém a qualidade da solução. O método foi avaliado em 88 instâncias de benchmark de três conjuntos clássicos. Os resultados demonstram eficiência computacional, resolvendo todas as instâncias em segundos comparado às centenas ou milhares de segundos exigidos pelos métodos do estado da arte. Para instˆancias com apenas pesos positivos, a abordagem alcançou um gap médio de 4,60% em relação às melhores soluções conhecidas, enquanto o gap médio geral foi de 9,10%, representando um trade-off favorável entre qualidade da solução e velocidade computacional.