|
Дискретный анализ и исследование операций, 2008, том 15, выпуск 4, страницы 30–43
(Mi da539)
|
|
|
|
Эта публикация цитируется в 13 научных статьях (всего в 13 статьях)
О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве
Э. Х. Гимади, Ю. В. Глазков, И. А. Рыков Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Рассматриваются две задачи выбора из множества векторов, состоящего из $n$ векторов в евклидовом пространстве $\mathbb R^k$, подмножества векторов мощности $m$ с максимальной нормой суммы. Предполагается, что координаты векторов целочисленны. С использованием техники динамического программирования построены новые точные алгоритмы решения этих задач, псевдополиномиальные при фиксированной размерности пространства. Новые алгоритмы (по сравнению с ранее известными) обладают определённым преимуществом: задача выбора решается быстрее при $m<(k/2)^k$, а с учётом дополнительного ограничения на порядок векторов время решения уменьшается в $k^{k-1}$ раз независимо от $m$. Библиогр. 5.
Ключевые слова:
выбор подмножества, евклидова метрика, временная сложность, псевдополиномиальный алгоритм, динамическое программирование.
Статья поступила: 16.03.2008 Переработанный вариант: 20.06.2008
Образец цитирования:
Э. Х. Гимади, Ю. В. Глазков, И. А. Рыков, “О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 15:4 (2008), 30–43; J. Appl. Industr. Math., 3:3 (2009), 343–352
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da539 https://www.mathnet.ru/rus/da/v15/i4/p30
|
Статистика просмотров: |
Страница аннотации: | 615 | PDF полного текста: | 131 | Список литературы: | 61 | Первая страница: | 11 |
|