|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
Новые верхние оценки для задачи максимальной выполнимости
А. С. Куликов, К. Куцков
Аннотация:
В работе приводятся сравнительно простые доказательства следующих новых верхних оценок для задач максимальной выполнимости:
$c^N$, где константа $c<2$, а $N$ – число переменных, для задачи MAX-SAT для формул константной плотности;
$2^{K/6}$, где $K$ – число клозов, для задачи MAX-2-SAT;
$2^{N/6,7}$ для задачи $(n,3)$-MAX-2-SAT.
Все оценки доказаны методом расщепления. Основными использующимися идеями являются техника запоминания клозов и использование комбинированных мер сложности.
Работа первого автора поддержана Российским фондом фундаментальных исследований, гранты 06–01–00502а и 08–01–00640а, и Фондом содействия отечественной науке.
Статья поступила: 11.03.2008
Образец цитирования:
А. С. Куликов, К. Куцков, “Новые верхние оценки для задачи максимальной выполнимости”, Дискрет. матем., 21:1 (2009), 139–157; Discrete Math. Appl., 19:2 (2009), 155–172
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1043https://doi.org/10.4213/dm1043 https://www.mathnet.ru/rus/dm/v21/i1/p139
|
Статистика просмотров: |
Страница аннотации: | 542 | PDF полного текста: | 228 | Список литературы: | 44 | Первая страница: | 13 |
|