Speaker
Sergei Anikin
(MIPT)
Description
This research addresses the well-known Max Cut problem, which has various applications both in machine learning and theoretical physics. The Max Cut problem is computationally NP-hard over general graphs. This research presents a novel empirical approach aimed at enhancing the quality of Max-Cut approximations within polynomial time bounds. While the problem is tractable for graphs with small tree-width, its solution over general graphs often relies on Semi-Definite Programming or Lovász-Schrijver relaxations. We achieve the described improvement of approximation quality by combining relaxation approaches and tree-width driven k-diagonal ideas
Primary authors
Mr
Ivan Voronin
Sergei Anikin
(MIPT)
