М. Ю. Хачай, М. И. Поберий, “Вычислительная сложность и аппроксимируемость серии геометрических задач о покрытии”, Тр. ИММ УрО РАН, 2012, том 18, номер 3,страницы 247

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

Вычислительная сложность и аппроксимируемость серии геометрических задач о покрытии

М. Ю. Хачай^ab, М. И. Поберий^b

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

Аннотация: Рассматривается серия геометрических задач о покрытии конечных подмножеств конечномерных числовых пространств семействами гиперплоскостей минимальной мощности. Обосновывается труднорешаемость и Max-SNP-трудность исследуемых задач.

Ключевые слова: $NP$-полная задача, полиномиальная сводимость, Max-SNP-трудная задача, $L$-редукция, полиномиальная приближенная схема.

УДК: 519.6

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