А. В. Пяткин, “О сложности задачи выбора подмножества векторов максимальной суммарной длины”, Дискретн. анализ и исслед. опер., 2009, том 16, выпуск 6,страницы 68

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

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

А. В. Пяткин^ab

^a Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск, Россия
^b Новосибирский государственный университет, г. Новосибирск, Россия

Аннотация: Рассматривается задача выбора подмножества векторов максимальной суммарной длины. В случае фиксированной размерности пространства эта задача является полиномиально разрешимой. Доказана NP-полнота задачи при нефиксированной размерности пространства. Библиогр. 6.

Ключевые слова: cуммирование векторов, сложность, NP-полнота.

УДК: 519.2+621.391

Статья поступила: 04.08.2009