Комитеты систем линейных неравенств

Рассматриваются концептуальные вопросы теории комитетных решающих правил, показана ее тесная связь с теорией обоснования принятия коллективных решений и обучением нейронных сетей. Отдельно рассмотрена задача о минимальном комитете несовместной системы ограничений, возникающая на этапе построения комитетного решающего правила с малым числом элементов. Известно, что в общем случае задача о минимальном комитете является NP-трудной. Получены результаты, касающиеся оценки вычислительной сложности задач, близких к этой задаче. Предложен также эффективный приближенный алгоритм решения задачи о минимальном комитете несовместной системы линейных неравенств. Обосновывается его корректность, указываются: оценка вычислительной сложности и гарантированная оценка точности.

Статья представлена к публикации членом редколлегии: А. И. Кибзун