Том 22, номер 3, 2015 г., Стр. 5−17

УДК 519.174
Гимади Э. Х., Рыков И. А.
Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы

Аннотация:
Представлен рандомизированный приближённый алгоритм для NP-трудной в сильном смысле задачи выбора из конечного семейства векторов в евклидовом пространстве заданного числа векторов с максимальной нормой суммы. Приведены условия его полиномиальности и асимптотической точности.
Ил. 1, библиогр. 18.

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

DOI: 10.17377/daio.2015.22.465

Гимади Эдуард Хайрутдинович ^1,2
Рыков Иван Александрович ¹
1. Институт математики им. С. Л. Соболева
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет
ул. Пирогова, 2, 630090 Новосибирск, Россия
e-mail: gimadi@math.nsc.ru, rykovweb@gmail.com

Статья поступила 21 октября 2014 г.
Исправленный вариант — 2 марта 2015 г.

Литература

[1] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 c.

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

[3] Гимади Э. Х., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Пробл. кибернетики. 1975. Вып. 31. C. 35–42.

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

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

[6] Гимади Э. Х., Рыков И. А. Приближённый рандомизированный алгоритм отыскания подмножества векторов с максимальной нормой суммы в многомерном евклидовом пространстве //Дискретная оптимизация и исследование операций: Мат. конф. (Алтай, 27 июня–3 июля 2010 г.). Новосибирск: Изд-во Ин-та математики, 2010. С. 102.

[7] Гимади Э. Х., Рыков И. А. Рандомизированный алгоритм отыскания подмножества векторов с максимальной нормой суммы в евклидовом пространстве // Тр. XV Байк. междунар. школы-семинара Методы оптимизации и их приложения.. Т. 4. Дискретная оптимизация. Иркутск: РИО ИДСТУ СО РАН, 2011. С. 76–81.

[8] Долгушев А. В., Кельманов А. В. Приближённый алгоритм решения одной задачи кластерного анализа // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 2. C. 29–40.

[9] Долгушев А. В., Кельманов А. В.,Шенмайер В. В. Приближённая полиномиальная схема для одной задачи кластерного анализа // Интеллектуализация обработки информации: Сб. докл. 9-й междунар. конф. (Республика Черногория, г. Будва, 16–22 сентября 2012 г.). М.: Торус Пресс, 2012. C. 242–244.

[10] Кельманов А. В., Хандеев В. И. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов // Журн. вычисл. математики и мат. физики. 2015. Т. 55, № 2. С. 335–344.

[11] Bern M., Eppstein D. Approximation algorithms for geometric problems // Approximation algorithms for NP-hard problems. Boston: PWS Publ. Co., 1997. P. 296–345.

[12] Bishop C. M. Pattern recognition and machine learning. New York: Springer, 2006. 738 p.

[13] James G., Witten D., Hastie T., Tibshirani R. An introduction to statistical learning. New York: Springer, 2013. 426 p.

[14] Jain A. K. Data clustering: 50 years beyond K-means // Pattern. Recognit. Lett. 2010. Vol. 31. P. 651–666.

[15] Flach P. Machine learning: The art and science of algorithms that make sense of data. New York: Cambridge Univ. Press, 2012. 396 p.

[16] Huber G. Notes: gamma function derivation of n-sphere volumes // Amer. Math. Monthly. 1982. Vol. 89, No. 5. P. 301–302.

[17] MacQueen J. B. Some methods for classification and analysis of multivariate observations // Proc. 5th Berkeley Symp. Math. Stat. Probab. Vol. 1. Berkeley, CA: Univ. California Press, 1967. P. 281–297.

[18] Rao M. R. Cluster analysis and mathematical programming // J. Amer. Stat. Assoc. 1971. Vol. 66. P. 622–626.