Heurística probabilística guiada pelos potenciais dos vértices para o problema do corte máximo

Abstract

The Max Cut Problem consists of dividing the vertices of a graph into two sets so that the sum of the edge weights between these two sets is as high as possible. The problem is NP-Hard and to the best of our knowledge there is still no method or work in the literature that has managed to obtain the optimal value of instances with large sizes. In this work we propose a new heuristic that is given by combining a local search, guided by the internal and external potentials of the vertices, with the use of probability to create an initial solution. We present computational experiments on 54 instances known from the literature and other created instances. The results obtained are compared with a work in the literature that is considered the best among those that also use probability to compose a resolution method for the max cut