|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины
В. В. Шенмайер Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Рассматривается следующая задача. Для заданного $n$-элементного множества векторов в $d$-мерном евклидовом пространстве найти подмножество, на котором достигается максимальное значение длины суммарного вектора. Предлагается алгоритм, позволяющий находить оптимальное решение этой задачи за время $O(n^{d-1}(d+\log n))$. В частности, если векторы входного множества лежат в одной плоскости, задача может быть решена за почти линейное время. Ил. 2, библиогр. 14.
Ключевые слова:
суммарный вектор, поиск подмножества векторов, евклидово пространство, оптимальное решение, полиномиальный алгоритм.
Статья поступила: 22.05.2016 Переработанный вариант: 10.05.2017
Образец цитирования:
В. В. Шенмайер, “Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 24:4 (2017), 111–129; J. Appl. Industr. Math., 11:4 (2017), 584–593
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da885 https://www.mathnet.ru/rus/da/v24/i4/p111
|
Статистика просмотров: |
Страница аннотации: | 356 | PDF полного текста: | 169 | Список литературы: | 31 | Первая страница: | 4 |
|