Том 15, номер 5, 2008 г., Стр. 20-34
УДК 519.2+621.391
А. В. Кельманов, А. В. Пяткин
Об одном варианте задачи выбора подмножества векторов
Аннотация:
Доказана NP-полнота задачи выбора подмножества «похожих» векторов, к которой сводится один из вариантов проблемы апостериорного (off-line) помехоустойчивого обнаружения в числовой последовательности неизвестного повторяющегося вектора в случае, когда помеха аддитивна. Обоснован приближённый полиномиальный алгоритм решения этой задачи с гарантированной оценкой точности в случае фиксированной размерности пространства.
Ключевые слова: числовая векторная последовательность, апостериорная обработка, повторяющийся вектор, оптимальное помехоустойчивое обнаружение, сложность, NP-полнота, приближённый алгоритм.
Кельманов Александр Васильевич 1
Пяткин Артём Валерьевич 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: kelm@math.nsc.ru, artem@math.nsc.ru
Статья поступила 1 апреля 2008 г.
