Speaker
Description
This article discusses the well-studied Max-Cut problem in graph theory, which has found applications in various fields, particularly Machine Learning, Theoretical physics (the Ising model), and VLSI design.
The original problem is NP-complete, and we call an effective solution such a polynomial algorithm that gives the answer closest to the true one.
For a long time, the best accuracy achievable by polynomial algorithms was at least half of the optimal cut. It was only in 1995 that Goemans and Williamson introduced a polynomial algorithm using semidefinite programming and randomized rounding, guaranteeing an approximation of $\approx 0.878$. This is the best possible approximation guarantee for the Max-Cut problem under the Unique games conjecture \cite{unique}.
In this article, we propose a novel approach to solving the Max-Cut problem with improved accuracy, in the particular case where the graph exhibits a treewidth bounded by a pre-fixed value, providing a number of heuristics.
