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

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

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


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




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

Ж. вычисл. матем. и матем. физ., 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

    ОТПРАВИТЬ: 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-кластеризации”, Сиб. журн. вычисл. матем., 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
    		• Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:163
    Литература:28
     
    Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021