RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., 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{http://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

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Э. Х. Гимади, А. В. Пяткин, И. А. Рыков, “О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности”, Дискретн. анализ и исслед. опер., 15:6 (2008), 11–19  mathnet  mathscinet  zmath; 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  crossref
    2. А. В. Долгушев, А. В. Кельманов, “Приближëнный алгоритм решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 18:2 (2011), 29–40  mathnet  mathscinet  zmath; 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  crossref
    3. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62  mathnet  crossref  mathscinet  elib; 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  crossref
    4. А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 21, № 3, 2015, 100–109  mathnet  mathscinet  elib; 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  crossref
    5. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40  mathnet  crossref  mathscinet  elib; 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  crossref
    6. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$-кластеризации”, Дискретн. анализ и исслед. опер., 23:3 (2016), 21–34  mathnet  crossref  mathscinet  elib; 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  crossref
    7. А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836  mathnet  crossref  elib; 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  crossref  isi
    8. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    9. В. В. Шенмайер, “Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 24:4 (2017), 111–129  mathnet  crossref  elib; V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Industr. Math., 11:4 (2017), 584–593  crossref
    10. 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  crossref  isi
    11. 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  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:460
    Полный текст:98
    Литература:47
    Первая стр.:11
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019