Название исследуемой задачи:	Tree-width Driven SDP for The Max-Cut Problem
Тип научной работы:	M1P
Авторы:	Аникин Сергей, Воронин Иван
Научный руководитель:	аспирант мехмата МГУ, Александр Булкин

Abstract

This paper addresses the well-known Max Cut problem, which has various applications both in machine learning and theoretical physics. The Max Cut problem is computationally intractable (NP hard) over general graphs. This paper 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 (SDP) or Lovász-Schrijver relaxations. We achieve the described improvement of approximation quality by combining relaxation approaches, the tree-width ideas and various heuristics described in the paper.

Research publications

Presentations at conferences on the topic of research

Software modules developed as part of the study

1. A python package mylib with all implementation here.
2. A code with all experiment visualisation here. Can use colab.