Схема бустинга в задачах комбинаторной оптимизации, индуцированных коллективными алгоритмами обучения

Игровой подход, обобщающий традиционную схему бустинга, применяется к построению приближенного полиномиального алгоритма для известной труднорешаемой задачи о минимальном аффинном комитете, разделяющем конечные подмножества вещественного линейного пространства фиксированной размерности при дополнительном условии общности положения разделяемых множеств (задача MASC-GP($n$)). Показано, что предложенный алгоритм обладает рекордной на данный момент гарантированной оценкой точности.

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