Том 24, номер 4, 2017 г., Стр. 111-129

УДК 519.16
Шенмайер В. В.
Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины

Аннотация:
Рассматривается следующая задача. Для заданного $n$-элементного множества векторов в $d$-мерном евклидовом пространстве найти подмножество, на котором достигается максимальное значение длины суммарного вектора. Предлагается алгоритм, позволяющий находить оптимальное решение этой задачи за время $O$($n^{d - 1}$ ($d$ + log $n$)). В частности, если векторы входного множества лежат в одной плоскости, задача может быть решена за почти линейное время.
Ил. 2, библиогр. 14.

Ключевые слова: суммарный вектор, поиск подмножества векторов, евклидово пространство, оптимальное решение, полиномиальный алгоритм.

DOI: 10.17377/daio.2017.24.541

Шенмайер Владимир Владимирович ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru

Статья поступила 22 мая 2016 г.
Исправленный вариант — 10 мая 2017 г.

Литература

[1] Бабурин А. Е., Гимади Э. Х., Глебов Н. И., Пяткин А. В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискрет. анализ и исслед. операций. Сер. 2. 2007. Т. 14, № 1.
С. 32–42.

[2] Бабурин А. Е., Пяткин А. В. О полиномиальных алгоритмах решения одной задачи суммирования векторов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 2. С. 3–10.

[3] Гимади Э. Х., Глазков Ю. В., Рыков И. А. О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 4. С. 30–43.

[4] Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. 2006. Т. 9, № 1. С. 55–74.

[5] Гимади Э. Х., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 6. С. 11–19.

[6] Пяткин А. В. О сложности задачи выбора подмножества векторов максимальной суммарной длины // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 6. С. 68–73.

[7] Шенмайер В. В. Решение евклидовых задач поиска подмножества векторов с использованием диаграмм Вороного // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 4. C. 102–115.

[8] Buck R. C. Partition of space // Am. Math. Mon. 1943. Vol. 50, No. 9. P. 541–544.

[9] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to algorithms. Cambridge, MA: MIT Press and McGraw-Hill, 2001. 1180 p.

[10] Edelsbrunner H., O’Rourke J., Seidel R. Constructing arrangements of lines and hyperplanes with applications // SIAM J. Comput. 1986. Vol. 15, No. 2. P. 341–363.

[11] Hwang F. K., Onn S., Rothblum U. G. A polynomial time algorithm for shaped partition problems // SIAM J. Optim. 1999. Vol. 10, No. 1. P. 70–81.

[12] Johnson D. S., Preparata F. P. The densest hemisphere problem // Theor. Comp. Sci. 1978. Vol. 6, No. 1. P. 93–107.

[13] Onn S., Schulman L. J. The vector partition problem for convex objective functions // Math. Oper. Res. 2001. Vol. 26, No. 3. P. 583–590.

[14] Onn S. Private communication. Nov. 2016.