|
Дискретн. анализ и исслед. опер., 2015, том 22, номер 3, страницы 5–17
(Mi da816)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы
Э. Х. Гимадиa, И. А. Рыковb a Институт математики им. С. Л. Соболева, пр. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
Аннотация:
Представлен рандомизированный приближённый алгоритм для NP-трудной в сильном смысле задачи выбора из конечного семейства векторов в евклидовом пространстве заданного числа векторов с максимальной нормой суммы. Приведены условия его полиномиальности и асимптотической точности. Ил. 1, библиогр. 18.
Ключевые слова:
поиск подмножества векторов, рандомизированный алгоритм, асимптотическая точность.
DOI:
https://doi.org/10.17377/daio.2015.22.465
Полный текст:
PDF файл (290 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2015, 9:3, 351–357
Реферативные базы данных:
Тип публикации:
Статья
УДК:
519.174 Статья поступила: 21.10.2014 Переработанный вариант: 02.03.2015
Образец цитирования:
Э. Х. Гимади, И. А. Рыков, “Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы”, Дискретн. анализ и исслед. опер., 22:3 (2015), 5–17; J. Appl. Industr. Math., 9:3 (2015), 351–357
Цитирование в формате AMSBIB
\RBibitem{GimRyk15}
\by Э.~Х.~Гимади, И.~А.~Рыков
\paper Рандомизированный алгоритм отыскания подмножества векторов с~максимальной евклидовой нормой их суммы
\jour Дискретн. анализ и исслед. опер.
\yr 2015
\vol 22
\issue 3
\pages 5--17
\mathnet{http://mi.mathnet.ru/da816}
\crossref{https://doi.org/10.17377/daio.2015.22.465}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3443295}
\elib{https://elibrary.ru/item.asp?id=23859889}
\transl
\jour J. Appl. Industr. Math.
\yr 2015
\vol 9
\issue 3
\pages 351--357
\crossref{https://doi.org/10.1134/S1990478915030060}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da816 http://mi.mathnet.ru/rus/da/v22/i3/p5
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
A. Kel'manov, V. Khandeev, “Some algorithms with guaranteed accuracy for 2-clustering problems with given center of one cluster”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 91–93
-
A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On complexity of searching a subset of vectors with shortest average under a cardinality restriction”, Analysis of Images, Social Networks and Texts, AIST 2016, Communications in Computer and Information Science, 661, ed. D. Ignatov, M. Khachay, V. Labunets, N. Loukachevitch, S. Nikolenko, A. Panchenko, A. Savchenko, K. Vorontsov, Springler, 2017, 51–57
|
Просмотров: |
Эта страница: | 221 | Полный текст: | 42 | Литература: | 37 | Первая стр.: | 13 |
|