The Max-Cut problem is the one of finding a maximum weight cut in a weighted graph. Because of the its great interest among the optimizers, several approaches, also of a quite diverse nature, have been proposed to find good or provably good solutions, which makes it also very interesting as a benchmark problem for new algorithmic ideas. Very recently the problem has received a lot of attention since a dedicated hardware, based on quantum annealing, has been realized that yields good solution in amazingly short times for some particular instances (the Chimera graphs). We review some of the exact optimization algorithms today available and how they behave compared to the new quantum approach.
Homepage of Giovanni Rinaldi