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

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

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



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






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


Труды Института математики и механики УрО РАН, 2019, том 25, номер 4, страницы 69–78
DOI: https://doi.org/10.21538/0134-4889-2019-25-4-69-78
(Mi timm1671)
 

Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость

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

a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский национальный исследовательский государственный университет
Список литературы:
Аннотация: В работе рассматривается задача кластеризации $N$-элементного множества точек в $d$-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти $2$-разбиение, минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно искомых центров. Центр одного кластера определяется как центроид (геометрический центр), а центр другого кластера является искомой точкой во входном множестве. Анализируется вариант задачи, в котором размеры (т. е. мощности) кластеров заданы, а их суммарный размер совпадает с размером входного множества. Доказано, что задача NP-трудна в сильном смысле. Установлено, что для нее не существует полностью полиномиальной аппроксимационной схемы, если P$\neq$ NP.
Ключевые слова: евклидово пространство, кластеризация, $2$-разбиение, квадратичный разброс, центр, центроид, медиана, сильная NP-трудность, несуществование полностью полиномиальной приближенной схемы, эффективная сводимость с сохранением точности.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 19-01-00308
18-31-00398
Сибирское отделение Российской академии наук 0314-2019-0014
0314-2019-0015
Министерство образования и науки Российской Федерации 5-100
Работа выполнена при финансовой поддержке РФФИ, проекты 19-01-00308 и 18-31-00398, программы ФНИ РАН, проекты 0314-2019-0014, 0314-2019-0015, а также программы Top-5-100 Министерства образования и науки РФ.
Поступила в редакцию: 12.08.2019
Исправленный вариант: 10.09.2019
Принята в печать: 16.09.2019
Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2021, Volume 313, Issue 1, Pages S117–S124
DOI: https://doi.org/10.1134/S0081543821030123
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16+519.85
MSC: 68W25, 68Q25
Образец цитирования: А. В. Кельманов, А. В. Пяткин, В. И. Хандеев, “Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость”, Тр. ИММ УрО РАН, 25, № 4, 2019, 69–78; Proc. Steklov Inst. Math. (Suppl.), 313, suppl. 1 (2021), S117–S124
Цитирование в формате AMSBIB
\RBibitem{KelPyaKha19}
\by А.~В.~Кельманов, А.~В.~Пяткин, В.~И.~Хандеев
\paper Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость
\serial Тр. ИММ УрО РАН
\yr 2019
\vol 25
\issue 4
\pages 69--78
\mathnet{http://mi.mathnet.ru/timm1671}
\crossref{https://doi.org/10.21538/0134-4889-2019-25-4-69-78}
\elib{https://elibrary.ru/item.asp?id=41455522}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2021
\vol 313
\issue , suppl. 1
\pages S117--S124
\crossref{https://doi.org/10.1134/S0081543821030123}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000501769500007}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85078544596}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/timm1671
  • https://www.mathnet.ru/rus/timm/v25/i4/p69
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Труды Института математики и механики УрО РАН
    Статистика просмотров:
    Страница аннотации:158
    PDF полного текста:40
    Список литературы:26
    Первая страница:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024