Методология решения комбинаторных задач о наименьшей системе представителей и родственных задач

В докладе рассматривается методология приближенного решения класса задач о наименьшей системе представителей и задач о покрытии на основе так называемых $\varepsilon$-сетей, предложенная Бронниманом и Гудричем и их последователями. Данный подход можно считать естественным приложением известной в теории статистического обучения техники бустинга к задачам комбинаторной оптимизации. Нами будут приведены серьезные авторские результаты, полученные на основе применения этой техники к другому классу задач о минимальном разделяющем комитете.