Том 15, номер 4, 2008 г., Стр. 30-43
УДК 519.8
Э. Х. Гимади, Ю. В. Глазков, И. А. Рыков
О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве
Аннотация:
Рассматриваются две задачи выбора из множества векторов, состоящего из$n$ векторов в евклидовом пространстве$\mathbb R^k$ , подмножества векторов мощности$m$ с максимальной нормой суммы. Предполагается, что координаты векторов целочисленны. С использованием техники динамического программирования построены новые точные алгоритмы решения этих задач, псевдополиномиальные при фиксированной размерности пространства. Новые алгоритмы (по сравнению с ранее известными) обладают определённым преимуществом: задача выбора решается быстрее при$m<(k/2)^k$ , а с учётом дополнительного ограничения на порядок векторов время решения уменьшается в$k^{k-1}$ раз независимо от$m$ .
Библиогр. 5.
Ключевые слова: выбор подмножества, евклидова метрика, временная сложность, псевдополиномиальный алгоритм, динамическое программирование.
Гимади Эдуард Хайрутдинович 1
Глазков Юрий Владимирович 1
Рыков Иван Александрович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, yg@ngs.ru, rykov@ledas.com
Статья поступила 16 марта 2008 г.
Исправленный вариант — 20 июня 2008 г.
