|
Труды Института математики и механики УрО РАН, 2012, том 18, номер 3, страницы 247–260
(Mi timm859)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Вычислительная сложность и аппроксимируемость серии геометрических задач о покрытии
М. Ю. Хачайab, М. И. Поберийb a Уральский федеральный университет
b Институт математики и механики УрО РАН
Аннотация:
Рассматривается серия геометрических задач о покрытии конечных подмножеств конечномерных числовых пространств семействами гиперплоскостей минимальной мощности. Обосновывается труднорешаемость и Max-SNP-трудность исследуемых задач.
Ключевые слова:
$NP$-полная задача, полиномиальная сводимость, Max-SNP-трудная задача, $L$-редукция, полиномиальная приближенная схема.
Поступила в редакцию: 26.03.2012
Образец цитирования:
М. Ю. Хачай, М. И. Поберий, “Вычислительная сложность и аппроксимируемость серии геометрических задач о покрытии”, Тр. ИММ УрО РАН, 18, № 3, 2012, 247–260; Proc. Steklov Inst. Math. (Suppl.), 283, suppl. 1 (2013), 64–77
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm859 https://www.mathnet.ru/rus/timm/v18/i3/p247
|
Статистика просмотров: |
Страница аннотации: | 281 | PDF полного текста: | 85 | Список литературы: | 52 | Первая страница: | 1 |
|