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

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

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



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






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


Тр. ИММ УрО РАН, 2017, том 23, номер 3, страницы 159–170 (Mi timm1446)  

Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера

А. В. Кельмановab, А. В. Мотковаb, В. В. Шенмайерa

a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский государственный университет

Аннотация: Рассматривается одна из труднорешаемых задач разбиения конечного множества точек евклидова пространства на два кластера. Критерием решения является минимум суммы по обоим кластерам взвешенных сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Центр одного из кластеров неизвестен и определяется как точка пространства, равная среднему значению элементов этого кластера (т. е. равная центроиду этого кластера). Центр другого кластера фиксирован в начале координат. Весовые множители для обеих внутрикластерных сумм заданы на входе. Предложен алгоритм приближенного решения задачи, основанный на адаптивном сеточном подходе поиска центра оптимального кластера. Показано, что алгоритм является полностью полиномиальной приближенной схемой (FPTAS) в случае фиксированной размерности пространства. В случае, когда размерность пространства не фиксирована, но ограничена медленно растущей функцией от мощности входного множества, алгоритм реализует полиномиальную аппроксимационную схему (PTAS).

Ключевые слова: евклидово пространство, кластеризация, $NP$-трудность, FPTAS, PTAS.

Финансовая поддержка Номер гранта
Российский научный фонд 16-11-10041
Работа выполнена при поддержке РНФ (проект 16-11-10041).


DOI: https://doi.org/10.21538/0134-4889-2017-23-3-159-170

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

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2018, 303, suppl. 1, 136–145

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

Тип публикации: Статья
УДК: 519.16+519.85
MSC: 68W25, 68Q25
Поступила в редакцию: 24.05.2017

Образец цитирования: А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170; Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145

Цитирование в формате AMSBIB
\RBibitem{KelMotShe17}
\by А.~В.~Кельманов, А.~В.~Моткова, В.~В.~Шенмайер
\paper Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера
\serial Тр. ИММ УрО РАН
\yr 2017
\vol 23
\issue 3
\pages 159--170
\mathnet{http://mi.mathnet.ru/timm1446}
\crossref{https://doi.org/10.21538/0134-4889-2017-23-3-159-170}
\elib{http://elibrary.ru/item.asp?id=29938008}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2018
\vol 303
\issue , suppl. 1
\pages 136--145
\crossref{https://doi.org/10.1134/S0081543818090146}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000453521100014}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timm1446
  • http://mi.mathnet.ru/rus/timm/v23/i3/p159

    ОТПРАВИТЬ: 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
  • Труды Института математики и механики УрО РАН
    Просмотров:
    Эта страница:128
    Полный текст:16
    Литература:15
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019