Хачай М. Ю.

Вычислительная сложность задач комитетной полиэдральной отделимости в пространствах фиксированной размерности

Журнал: 
Страница: 
218
В работе показано, что задача о минимальном аффинном разделяющем комитете (JNIASC), тесно связанная с процедурой обучения распознаванию в классе полиэдральных решающих правил, остается труднорешаемой, даже будучи сформулированной в пространстве произвольной фиксированной размерности n > 1, причем труднорешаемость задачи не обусловлена вырожденностью разделяемых множеств.

О вычислительной и аппроксимационной сложности задачи о минимальном аффинном разделяющем комитете

Авторы: 
Журнал: 
Страница: 
34
Рассматриваются две комбинаторных задачи, связанные с обучением распознаванию образов: задача проверки существования аффинного разделяющего комитета из 3-х элементов (3-А8С) и задача о минимальном по числу элементов аффинном разделяющем комитете (МА8С). Показано, что задача 3-А8С ЖР-полна, а задача МА8С .ЛГР-трудна и не принадлежит классу Арх. Обсуждается новый приближенный алгоритм для задачи МА8С.

Об аппроксимационной сложности задачи о минимальном комитете

Авторы: 
Журнал: 
Страница: 
78
Изучается комбинаторная задача о минимальном комитете. Известно, что эта задача является ΝΡ-трудной. В статье показано, что если справедливо условие ΝΡ∉ΤΙΜΕ(mO(log log m)), то для произвольного ε > 0 не существует приближенного алгоритма задачи M F S с точностью (1 — ε) ln m.