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

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

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



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






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


Дискретн. анализ и исслед. опер., 2008, том 15, номер 6, страницы 11–19 (Mi da553)  

Эта публикация цитируется в 13 научных статьях (всего в 13 статьях)

О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности

Э. Х. Гимадиab, А. В. Пяткинab, И. А. Рыковab

a Институт математики им. С. Л. Соболева СО РАН
b Новосибирский государственный университет

Аннотация: Рассмотрены задачи, связанные с выбором из конечного семейства векторов в евклидовом пространстве $\mathbb R^k$ подмножества векторов. В качестве (максимизируемых) целевых функций задач выступают норма суммы и усреднённый квадрат нормы суммы. Для решения этих задач разработаны точные комбинаторные алгоритмы с временно́й сложностью $O(k^2n^{2k})$. Тем самым доказана полиномиальная разрешимость данных задач при фиксированном $k$. Библиогр. 6.

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

Полный текст: PDF файл (254 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2010, 4:1, 48–53

Реферативные базы данных:

УДК: 519.8
Статья поступила: 18.07.2008
Переработанный вариант: 14.10.2008

Образец цитирования: Э. Х. Гимади, А. В. Пяткин, И. А. Рыков, “О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности”, Дискретн. анализ и исслед. опер., 15:6 (2008), 11–19; J. Appl. Industr. Math., 4:1 (2010), 48–53

Цитирование в формате AMSBIB
\RBibitem{GimPyaRyk08}
\by Э.~Х.~Гимади, А.~В.~Пяткин, И.~А.~Рыков
\paper О полиномиальной разрешимости некоторых задач выбора подмножества векторов в~евклидовом пространстве фиксированной размерности
\jour Дискретн. анализ и исслед. опер.
\yr 2008
\vol 15
\issue 6
\pages 11--19
\mathnet{http://mi.mathnet.ru/da553}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2543143}
\zmath{https://zbmath.org/?q=an:1249.90342}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 1
\pages 48--53
\crossref{https://doi.org/10.1134/S1990478910010084}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77949881390}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da553
  • http://mi.mathnet.ru/rus/da/v15/i6/p11

    ОТПРАВИТЬ: 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. А. В. Пяткин, “О сложности задачи выбора подмножества векторов максимальной суммарной длины”, Дискретн. анализ и исслед. опер., 16:6 (2009), 68–73  mathnet  mathscinet  zmath  elib; A. V. Pyatkin, “On the complexity of the maximum sum length vectors subset choice problem”, J. Appl. Industr. Math., 4:4 (2010), 549–552  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. А. В. Кельманов, В. И. Хандеев, “Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 20:4 (2013), 36–45  mathnet  mathscinet; A. V. Kelmanov, V. I. Khandeev, “A $2$-approximation polynomial algorithm for one clustering problem”, J. Appl. Industr. Math., 7:4 (2013), 515–521  crossref
    4. Э. Х. Гимади, И. А. Рыков, “Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы”, Дискретн. анализ и исслед. опер., 22:3 (2015), 5–17  mathnet  crossref  mathscinet  elib; E. Kh. Gimadi, I. A. Rykov, “A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum”, J. Appl. Industr. Math., 9:3 (2015), 351–357  crossref
    5. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 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
    6. А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 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
    7. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    8. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 23:4 (2016), 102–115  mathnet  crossref  mathscinet  elib; V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566  crossref
    9. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    10. В. В. Шенмайер, “Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 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
    11. 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
    12. 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
    13. Kel'manov A. Motkova A. Shenmaier V., “An Approximation Scheme For a Weighted Two-Cluster Partition Problem”, Analysis of Images, Social Networks and Texts, Aist 2017, Lecture Notes in Computer Science, 10716, ed. VanDerAalst W. Ignatov D. Khachay M. Kuznetsov S. Lempitsky V. Lomazova I. Loukachevitch N. Napoli A. Panchenko A. Pardalos P. Savchenko A. Wasserman S., Springer International Publishing Ag, 2018, 323–333  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:424
    Полный текст:83
    Литература:34
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019