Loading [MathJax]/jax/output/CommonHTML/jax.js
Журнал вычислительной математики и математической физики
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

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

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



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






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


Журнал вычислительной математики и математической физики, 2016, том 56, номер 3, страницы 498–504
DOI: https://doi.org/10.7868/S0044466916030091
(Mi zvmmf10352)
 

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

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

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

a 630090 Новосибирск, пр. Ак. Коптюга, 4, Ин-т матем. СО РАН
b 630090 Новосибирск, ул. Пирогова, 2, НГУ
Список литературы:
Аннотация: Рассматриваются задачи двухкластерного разбиения конечного множества точек евклидова пространства. В этих задачах минимизируются следующие критерии: (1) сумма по обоим кластерам суммы квадратов попарных расстояний между элементами кластера, (2) сумма умноженных на мощность кластеров сумм квадратов расстояний от элементов кластера до его геометрического центра. Под геометрическим центром кластера (центроидом) понимается точка пространства, равная среднему значению элементов кластера. Кроме того, рассматривается близкая к (2) в постановочном плане задача, в которой на входе задан желаемый центр одного из кластеров, а центр другого, как и в задаче (2), неизвестен (является оптимизируемой переменной). Анализируются варианты задач, в которых мощности кластеров: (1) заданы на входе, (2) неизвестны. Установлено, что все рассмотренные задачи NP-трудны в сильном смысле и для общего случая этих задач не существует полностью полиномиальной приближенной схемы (FPTAS), если PNP. Библ. 21.
Ключевые слова: кластерный анализ, разбиение конечного множества, евклидово пространство, минимум суммы квадратов расстояний между элементами кластера, NP-трудная задача, экстремальные задачи.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462_а
15-01-00976_а
16-07-00168_а
Работа выполнена при финансовой поддержке РФФИ (коды проектов № 15-01-00462, № 15-01-00976, № 16-07-00168).
Поступила в редакцию: 07.04.2015
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2016, Volume 56, Issue 3, Pages 491–497
https://link.springer.com/article/10.1134/S096554251603009X
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.7
Образец цитирования: А. В. Кельманов, А. В. Пяткин, “О сложности некоторых квадратичных евклидовых задач 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{https://elibrary.ru/item.asp?id=25678781}
\transl
\jour Comput. Math. Math. Phys.
\yr 2016
\vol 56
\issue 3
\pages 491--497
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf10352
  • https://www.mathnet.ru/rus/zvmmf/v56/i3/p498
  • Эта публикация цитируется в следующих 10 статьяx:
    1. А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации”, Сиб. журн. вычисл. матем., 22:2 (2019), 121–136  mathnet  crossref  elib; A. V. Kel'manov, A. V. Panasenko, V. I. Khandeev, “Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems”, Num. Anal. Appl., 12:2 (2019), 105–115  crossref  isi
    2. A. Panasenko, “A ptas for one cardinality-weighted 2-clustering problem”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, ed. M. Khachay, Y. Kochetov, P. Pardalos, Springer, 2019, 581–592  crossref  mathscinet  zmath  isi
    3. А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Рандомизированные алгоритмы для некоторых труднорешаемых задач кластеризации конечного множества точек евклидова пространства”, Ж. вычисл. матем. и матем. физ., 59:5 (2019), 895–904  mathnet  crossref  elib; A. V. Kel'manov, A. V. Panasenko, V. I. Khandeev, “Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space”, Comput. Math. Math. Phys., 59:5 (2019), 842–850  crossref  isi
    4. 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
    5. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib; A. V. Kel'manov, A. V. Motkova, V. V. Shenmaier, “Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster”, Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145  crossref  isi
    6. A. Pyatkin, D. Aloise, N. Mladenovic, “NP-hardness of balanced minimum sum-of-squares clustering”, Pattern Recognit. Lett., 97 (2017), 44–45  crossref  adsnasa  isi  elib  scopus
    7. 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
    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 2017, IEEE, 2017, 94–96  crossref  isi  scopus
    9. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $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
    10. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Статистика просмотров:
    Страница аннотации:308
    PDF полного текста:49
    Список литературы:63
    Первая страница:10
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025