RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики и механики УрО РАН // Архив

Тр. ИММ УрО РАН, 2013, том 19, номер 2, страницы 231–236 (Mi timm948)

Эта публикация цитируется в 3 статьях

Бустинг и полиномиальная аппроксимируемость задачи о минимальном аффинном разделяющем комитете

Вл. Д. Мазуровab, М. Ю. Хачайba

a Институт математики и механики УрО РАН
b Уральский федеральный университет

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

Ключевые слова: задача о минимальном аффинном разделяющем комитете, бустинг, полиномиальный приближенный алгоритм, точность аппроксимации.

УДК: 519.68

Поступила в редакцию: 12.02.2013



Реферативные базы данных:


© МИАН, 2024