Том 15, номер 6, 2008 г., Стр. 11-19
УДК 519.8
Э. Х. Гимади, А. В. Пяткин, И. А. Рыков
О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности
Аннотация:
Рассмотрены задачи, связанные с выбором из конечного семейства векторов в евклидовом пространстве$\mathbb R^k$ подмножества векторов. В качестве (максимизируемых) целевых функций задач выступают норма суммы и усреднённый квадрат нормы суммы. Для решения этих задач разработаны точные комбинаторные алгоритмы с временно́й сложностью$O(k^2n^{2k})$ . Тем самым доказана полиномиальная разрешимость данных задач при фиксированном$k$ .
Библиогр. 6.
Ключевые слова: подмножество векторов, евклидово пространство, полиномиальная разрешимость.
Гимади Эдуард Хайрутдинович 1
Пяткин Артём Валерьевич 1
Рыков Иван Александрович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, artem@math.nsc.ru, rykov@math.nsc.ru
Статья поступила 18 июля 2008 г.
Исправленный вариант — 14 октября 2008 г.
