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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2016, том 56, номер 3, страницы 498–504 (Mi zvmmf10352)  

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

О сложности некоторых квадратичных евклидовых задач 2-кластеризации

А. В. Кельмановab, А. В. Пяткинab

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

Аннотация: Рассматриваются задачи двухкластерного разбиения конечного множества точек евклидова пространства. В этих задачах минимизируются следующие критерии: (1) сумма по обоим кластерам суммы квадратов попарных расстояний между элементами кластера, (2) сумма умноженных на мощность кластеров сумм квадратов расстояний от элементов кластера до его геометрического центра. Под геометрическим центром кластера (центроидом) понимается точка пространства, равная среднему значению элементов кластера. Кроме того, рассматривается близкая к (2) в постановочном плане задача, в которой на входе задан желаемый центр одного из кластеров, а центр другого, как и в задаче (2), неизвестен (является оптимизируемой переменной). Анализируются варианты задач, в которых мощности кластеров: (1) заданы на входе, (2) неизвестны. Установлено, что все рассмотренные задачи NP-трудны в сильном смысле и для общего случая этих задач не существует полностью полиномиальной приближенной схемы (FPTAS), если $\mathrm{P\ne NP}$. Библ. 21.

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462_а
15-01-00976_а
16-07-00168_а
Работа выполнена при финансовой поддержке РФФИ (коды проектов № 15-01-00462, № 15-01-00976, № 16-07-00168).


DOI: https://doi.org/10.7868/S0044466916030091

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2016, 56:3, 491–497

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

Тип публикации: Статья
УДК: 519.7
Поступила в редакцию: 07.04.2015

Образец цитирования: А. В. Кельманов, А. В. Пяткин, “О сложности некоторых квадратичных евклидовых задач 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:3 (2016), 498–504; Comput. Math. Math. Phys., 56:3 (2016), 491–497

Цитирование в формате AMSBIB
\RBibitem{KelPya16}
\by А.~В.~Кельманов, А.~В.~Пяткин
\paper О сложности некоторых квадратичных евклидовых задач 2-кластеризации
\jour Ж. вычисл. матем. и матем. физ.
\yr 2016
\vol 56
\issue 3
\pages 498--504
\mathnet{http://mi.mathnet.ru/zvmmf10352}
\crossref{https://doi.org/10.7868/S0044466916030091}
\elib{http://elibrary.ru/item.asp?id=25678781}
\transl
\jour Comput. Math. Math. Phys.
\yr 2016
\vol 56
\issue 3
\pages 491--497


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf10352
  • http://mi.mathnet.ru/rus/zvmmf/v56/i3/p498

    ОТПРАВИТЬ: 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$-кластеризации”, Дискретн. анализ и исслед. опер., 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
    2. A. Kel'manov, A. Motkova, “A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem”, Discrete Optimization and Operations Research, Lecture Notes in Computer Science, 9869, eds. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, Springer Int Publishing Ag, 2016, 182–192  crossref  mathscinet  zmath  isi  scopus
    3. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    4. A. Pyatkin, D. Aloise, N. Mladenovic, “NP-hardness of balanced minimum sum-of-squares clustering”, Pattern Recognit. Lett., 97 (2017), 44–45  crossref  isi
    5. A. Kel'manov, “Efficient approximation algorithms for some NP-hard problems of partitioning a set and a sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, IEEE, 2017, 87–90  crossref  isi
    6. 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 2017, IEEE, 2017, 94–96  crossref  isi
    7. A. Kel'manov, A. Motkova, V. Shenmaier, “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. W. VanDerAalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, Springer, 2018, 323–333  crossref  isi  scopus
    8. Kel'manov V A. Panasenko V A. Khandeev I V., “Exact Algorithms of Search For a Cluster of the Largest Size in Two Integer 2-Clustering Problems”, Numer. Anal. Appl., 12:2 (2019), 105–115  crossref  isi
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:129
    Полный текст:8
    Литература:34
    Первая стр.:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019