И. Близнец (Академический университет)

Алгоритмы для задачи максимальной выполнимости и некоторых частных случаев

В докладе будут рассказаны некоторые алгоритмы касающиеся задачи MAX-SAT. А именно:
1) Алгоритм Вильямса для MAX-2-SAT.
2) Простой алгоритм для (n,3)-MAX-SAT, с оценкой времени работы в зависимости от количества клозов.
3) Обзор самого быстрого алгоритма для MAX-SAT, предложенного Ченом и Канжем (Jianer Chen, Iyad A. Kanj).