|
|
Дискретн. анализ и исслед. опер., 2008, том 15, номер 4, страницы 30–43
(Mi da539)
|
 |
|
 |
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)
О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве
Э. Х. Гимади, Ю. В. Глазков, И. А. Рыков
Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Рассматриваются две задачи выбора из множества векторов, состоящего из $n$ векторов в евклидовом пространстве $\mathbb R^k$, подмножества векторов мощности $m$ с максимальной нормой суммы. Предполагается, что координаты векторов целочисленны. С использованием техники динамического программирования построены новые точные алгоритмы решения этих задач, псевдополиномиальные при фиксированной размерности пространства. Новые алгоритмы (по сравнению с ранее известными) обладают определённым преимуществом: задача выбора решается быстрее при $m<(k/2)^k$, а с учётом дополнительного ограничения на порядок векторов время решения уменьшается в $k^{k-1}$ раз независимо от $m$. Библиогр. 5.
Ключевые слова:
выбор подмножества, евклидова метрика, временная сложность, псевдополиномиальный алгоритм, динамическое программирование.
 Полный текст:
PDF файл (265 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2009, 3:3, 343–352
Реферативные базы данных:
  
УДК:
519.8
Статья поступила: 16.03.2008
Переработанный вариант: 20.06.2008
Образец цитирования:
Э. Х. Гимади, Ю. В. Глазков, И. А. Рыков, “О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 15:4 (2008), 30–43; J. Appl. Industr. Math., 3:3 (2009), 343–352
Цитирование в формате AMSBIB
\RBibitem{GimGlaRyk08}
\by Э.~Х.~Гимади, Ю.~В.~Глазков, И.~А.~Рыков
\paper О двух задачах выбора подмножества векторов с~целочисленными координатами с~максимальной нормой суммы в~евклидовом пространстве
\jour Дискретн. анализ и исслед. опер.
\yr 2008
\vol 15
\issue 4
\pages 30--43
\mathnet{http://mi.mathnet.ru/da539}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2543598}
\zmath{https://zbmath.org/?q=an:1249.90171}
\transl
\jour J. Appl. Industr. Math.
\yr 2009
\vol 3
\issue 3
\pages 343--352
\crossref{https://doi.org/10.1134/S1990478909030041}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-70349150916}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da539 http://mi.mathnet.ru/rus/da/v15/i4/p30
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Э. Х. Гимади, А. В. Пяткин, И. А. Рыков, “О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности”, Дискретн. анализ и исслед. опер., 15:6 (2008), 11–19
 ; E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension”, J. Appl. Industr. Math., 4:1 (2010), 48–53 -
А. В. Долгушев, А. В. Кельманов, “Приближëнный алгоритм решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 18:2 (2011), 29–40 ; A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for one problem of cluster analysis”, J. Appl. Industr. Math., 5:4 (2011), 551–558
-
А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62
 ; A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502 -
А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 21, № 3, 2015, 100–109 ; A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56
 -
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40 ; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219
-
А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$-кластеризации”, Дискретн. анализ и исслед. опер., 23:3 (2016), 21–34 ; A. V. Kel'manov, A. V. Motkova, “Exact pseudopolinomial algorithms for a balanced $2$-clustering problem”, J. Appl. Industr. Math., 10:3 (2016), 349–355
-
А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836 ; A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Comput. Math. Math. Phys., 56:10 (2016), 1813–1817
-
А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170 ; A. V. Kel'manov, A. V. Motkova, V. V. Shenmaier, “Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster”, Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145
-
В. В. Шенмайер, “Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 24:4 (2017), 111–129 ; V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Industr. Math., 11:4 (2017), 584–593
-
Kel'manov A. Khandeev V., “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
-
Eremeev A.V. Kel'manov A.V. Pyatkin A.V., “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. Ignatov D. Khachay M. Labunets V. Loukachevitch N. Nikolenko S. Panchenko A. Savchenko A. Vorontsov K., Springer International Publishing Ag, 2017, 51–57
|
| Просмотров: |
| Эта страница: | 496 | | Полный текст: | 112 | | Литература: | 48 | | Первая стр.: | 11 |
|
Пользовательское соглашение