СХЕМА БУСТИНГА В ЗАДАЧАХ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ, ИНДУЦИРОВАННЫХ КОЛЛЕКТИВНЫМИ АЛГОРИТМАМИ ОБУЧЕНИЯ

摘要

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