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