Приближенный алгоритм для задачи минимизации полиномов от булевых переменных

Рассматриваются задача минимизации полиномов от булевых переменных и эквивалентные ей задача выбора множества строк и двухуровневая задача размещения. Для решения этих задач предлагается приближенный алгоритм, включающий получение нижней оценки значений целевых функций рассматриваемых задач. Алгоритм вычисления нижней оценки обобщает известную процедуру подъема для простейшей задачи размещения и состоит в построении так называемой тупиковой матрицы. Приближенное решение получается с использованием свойств этой матрицы. Приводятся результаты численных экспериментов с алгоритмом, демонстрирующие точность получаемых приближенных решений.
Библиогр. 8