Аннотация:
Исследуется труднорешаемая задача о минимальном аффинном разделяющем комитете, заданная в пространстве фиксированной размерности $n>1$ при дополнительном ограничении общности положения разделяемых множеств (MASC-GP($n$)). Применяя традиционный для бустинга игровой подход к исследованию семейства максимальных по включению отделимых подмножеств, строится полиномиальный приближенный алгоритм для задачи с гарантированной оценкой точности $O((m/n\ln m)^{1/2})$, где $m$ – мощность разделяемого множества.