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

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

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



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






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


Дискретн. анализ и исслед. опер., 2013, том 20, номер 4, страницы 36–45 (Mi da738)  

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

Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа

А. В. Кельмановab, В. И. Хандеевb

a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

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

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2013, 7:4, 515–521

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

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

Образец цитирования: А. В. Кельманов, В. И. Хандеев, “Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 20:4 (2013), 36–45; J. Appl. Industr. Math., 7:4 (2013), 515–521

Цитирование в формате AMSBIB
\RBibitem{KelKha13}
\by А.~В.~Кельманов, В.~И.~Хандеев
\paper Полиномиальный алгоритм с~оценкой точности~$2$ для решения одной задачи кластерного анализа
\jour Дискретн. анализ и исслед. опер.
\yr 2013
\vol 20
\issue 4
\pages 36--45
\mathnet{http://mi.mathnet.ru/da738}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3114911}
\transl
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 4
\pages 515--521
\crossref{https://doi.org/10.1134/S1990478913040066}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da738
  • http://mi.mathnet.ru/rus/da/v20/i4/p36

    ОТПРАВИТЬ: 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. А. В. Орлов, “Численный поиск глобальных решений в задачах несимметричной билинейной отделимости”, Дискретн. анализ и исслед. опер., 22:1 (2015), 64–85  mathnet  crossref  mathscinet  elib
    2. А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 55:6 (2015), 1076–1085  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, S. A. Khamidullin, “An approximation polynomial-time algorithm for a sequence bi-clustering problem”, Comput. Math. Math. Phys., 55:6 (2015), 1068–1076  crossref  isi  elib
    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. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 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
    5. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
    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. 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
    8. A. Kel'manov, A. Motkova, “An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 94–96  crossref  isi
    9. 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
    10. А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:203
    Полный текст:63
    Литература:39
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019