А. Головнев (Академический университет)

Эффективное решение MAX-2-SAT

В докладе будут рассмотрены лучшие известные алгоритмы для задач MAX
2-SAT, MAX 2-CSP, MAX CUT.
Будут предложены новые алгоритмы решения этих задач. В частности,
будет рассмотрен алгоритм решения задачи MAX 2-SAT с оценкой сложности
$O^*(2^{n(1-3.677/(d+1))})$.