|
Ж. вычисл. матем. и матем. физ., 2018, том 58, номер 1, страницы 136–142
(Mi zvmmf10665)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров
А. В. Кельмановab, А. В. Мотковаab a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. им. Соболева
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирский гос. ун-т
Аннотация:
Рассматривается NP-трудная в сильном смысле задача двухкластерного разбиения конечного множества точек евклидова пространства. Критерием решения является минимум суммы по обоим кластерам взвешенных сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Веса сумм равны мощностям искомых кластеров. Центр одного из кластеров задан на входе, а центр другого неизвестен и определяется как точка пространства, равная среднему значению элементов кластера. Анализируется вариант задачи, в котором мощности кластеров заданы на входе. Построен 2-приближенный полиномиальный алгоритм решения задачи. Библ. 25.
Ключевые слова:
евклидово пространство, взвешенная 2-кластеризация, NP-трудность, 2-приближенный полиномиальный алгоритм.
Финансовая поддержка |
Номер гранта |
Российский научный фонд  |
16-11-10041 |
Работа выполнена при финансовой поддержке РНФ (код проекта 16-11-10041). |
DOI:
https://doi.org/10.7868/S0044466918010076
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2018, 58:1, 130–136
Реферативные базы данных:
Тип публикации:
Статья
УДК:
519.7 Поступила в редакцию: 18.06.2016 Исправленный вариант: 20.07.2017
Образец цитирования:
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142; Comput. Math. Math. Phys., 58:1 (2018), 130–136
Цитирование в формате AMSBIB
\RBibitem{KelMot18}
\by А.~В.~Кельманов, А.~В.~Моткова
\paper Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров
\jour Ж. вычисл. матем. и матем. физ.
\yr 2018
\vol 58
\issue 1
\pages 136--142
\mathnet{http://mi.mathnet.ru/zvmmf10665}
\crossref{https://doi.org/10.7868/S0044466918010076}
\elib{https://elibrary.ru/item.asp?id=32282721}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 1
\pages 130--136
\crossref{https://doi.org/10.1134/S0965542518010074}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000426674100009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042701688}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/zvmmf10665 http://mi.mathnet.ru/rus/zvmmf/v58/i1/p136
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации”, Сиб. журн. вычисл. матем., 22:2 (2019), 121–136
; 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
|
Просмотров: |
Эта страница: | 148 | Литература: | 24 |
|