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

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

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



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






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


Дискретн. анализ и исслед. опер., 2011, том 18, номер 2, страницы 29–40 (Mi da644)  

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

Приближëнный алгоритм решения одной задачи кластерного анализа

А. В. Долгушевa, А. В. Кельмановab

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

Аннотация: Предложен 2-приближённый алгоритм для труднорешаемой задачи, к которой сводится одна из проблем разбиения множества векторов евклидова пространства на два подмножества (кластера) по критерию минимума суммы квадратов расстояний. Библиогр. 7.

Ключевые слова: поиск подмножества векторов, кластерный анализ, NP-трудность, эффективный приближённый алгоритм.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2011, 5:4, 551–558

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

Тип публикации: Статья
УДК: 519.2+621.391
Статья поступила: 26.12.2010
Переработанный вариант: 18.01.2011

Образец цитирования: А. В. Долгушев, А. В. Кельманов, “Приближëнный алгоритм решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 18:2 (2011), 29–40; J. Appl. Industr. Math., 5:4 (2011), 551–558

Цитирование в формате AMSBIB
\RBibitem{DolKel11}
\by А.~В.~Долгушев, А.~В.~Кельманов
\paper Приближ\"eнный алгоритм решения одной задачи кластерного анализа
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 2
\pages 29--40
\mathnet{http://mi.mathnet.ru/da644}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2841699}
\zmath{https://zbmath.org/?q=an:1249.90186}
\transl
\jour J. Appl. Industr. Math.
\yr 2011
\vol 5
\issue 4
\pages 551--558
\crossref{https://doi.org/10.1134/S1990478911040107}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-82655170461}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da644
  • http://mi.mathnet.ru/rus/da/v18/i2/p29

    ОТПРАВИТЬ: 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. А. В. Кельманов, В. И. Хандеев, “Полиномиальный алгоритм с оценкой точности $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
    2. Э. Х. Гимади, И. А. Рыков, “Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы”, Дискретн. анализ и исслед. опер., 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
    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. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339  crossref  isi  elib
    6. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340  mathnet  crossref  elib; A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341  crossref  isi
    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. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $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
    9. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 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
    10. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 2017, № 1, 80–90  mathnet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Autom. Remote Control, 78:1 (2017), 67–74  crossref  isi
    11. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    12. 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  crossref  isi
    13. 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  crossref  mathscinet  isi  scopus
    14. А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142  mathnet  crossref  elib; A. V. Kel'manov, A. V. Motkova, “Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center”, Comput. Math. Math. Phys., 58:1 (2018), 130–136  crossref  isi
    15. 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, eds. 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:310
    Полный текст:84
    Литература:37
    Первая стр.:6
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019