Том 14, серия 2, номер 1, 2007 г., Стр. 32–42
УДК 519.854
А. Е. Бабурин, Э. Х. Гимади, Н. И. Глебов, А. В. Пяткин
Задача отыскания подмножества векторов с максимальным суммарным весом
Аннотация:
Доказана NP-трудность дискретных оптимизационных задач, связанных с выбором из конечного семейства векторов в евклидовом пространстве подмножества векторов с максимальной нормой суммы. Предложены приближённые алгоритмы и получены оценки для относительной погрешности и временно?й сложности. В случае фиксированной размерности пространства построена полиномиальная аппроксимационная схема. Выделен подкласс задач, для которых за псевдополиномиальное время отыскивается точное решение. Полученные результаты могут быть использованы для решения задачи выбора фиксированного числа фрагментов в числовой последовательности квазипериодически повторяющегося фрагмента при заданном числе повторов.
Библ. 4.
Бабурин А. Е. 1
Гимади Э. Х. 1
Глебов Н. И. 1
Пяткин А. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru
Статья поступила 7 декабря 2006 г.
Исправленный вариант — 16 мая 2007 г.
