Aplicação de aprendizado de máquina supervisionado para o problema do corte máximo em grafos

Abstract

This study focuses on the creation of supervised models, coupled with the tuning of their hyperparameters, to address the Max-Cut Problem. Due to the NP-hard complexity of this problem, even for instances of intermediate size, finding an optimal solution poses a computational challenge. However, there are several applications of this problem in areas such as social network analysis, data clustering, image segmentation, and VLSI chip design, which continue to motivate researchers. The literature presents innovative methods, including those based on pointer networks with supervised and reinforcement learning, as well as approaches utilizing Neural Networks in Graphs. These methods represent promising advancements in solving this problem, thus providing potential solutions for its resolution.