Метод исключения ограничений для задачи о комитете

Предлагается метод сведения задачи нахождения $q$-членного $p$-комитета произвольной конечной системы множеств к той же задаче для системы множеств меньшей мощности и с меньшим числом максимальных по включению подсистем с непустым пересечением. При $p=\frac12$ для несовместной системы линейных неравенств в $\mathbb R^n$ дается эффективная реализация этого метода, сложность которой является полиномом по числу неравенств и числу членов комитета, но зависит экспоненциально от размерности пространства. Для этой реализации приводятся результаты вычислительного эксперимента при $n=2,3$.

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