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

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

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



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






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


Тр. ИММ УрО РАН, 2015, том 21, номер 3, страницы 100–109 (Mi timm1202)  

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

Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера

А. В. Долгушевa, А. В. Кельмановab, В. В. Шенмайерb

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

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

Ключевые слова: кластерный анализ, евклидово пространство, $np$-трудная задача.

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

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2016, 295, suppl. 1, 47–56

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

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

Образец цитирования: А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 21, № 3, 2015, 100–109; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56

Цитирование в формате AMSBIB
\RBibitem{DolKelShe15}
\by А.~В.~Долгушев, А.~В.~Кельманов, В.~В.~Шенмайер
\paper Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера
\serial Тр. ИММ УрО РАН
\yr 2015
\vol 21
\issue 3
\pages 100--109
\mathnet{http://mi.mathnet.ru/timm1202}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3468093}
\elib{http://elibrary.ru/item.asp?id=24156699}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2016
\vol 295
\issue , suppl. 1
\pages 47--56
\crossref{https://doi.org/10.1134/S0081543816090066}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000394441400006}


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

    ОТПРАВИТЬ: 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-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340  mathnet  crossref  elib; A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341  crossref  isi
    2. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  crossref
    3. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $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
    4. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 23:4 (2016), 102–115  mathnet  crossref  mathscinet  elib; V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566  crossref
    5. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 2017, № 1, 80–90  mathnet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Autom. Remote Control, 78:1 (2017), 67–74  crossref  isi
    6. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 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
    7. 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. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, Springer, 2018, 323–333  crossref  isi  scopus
    8. А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142  mathnet  crossref  elib; A. V. Kel'manov, A. V. Motkova, “Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center”, Comput. Math. Math. Phys., 58:1 (2018), 130–136  crossref  isi
    9. В. В. Шенмайер, “Сложность и аппроксимация задачи о длиннейшем суммарном векторе”, Ж. вычисл. матем. и матем. физ., 58:6 (2018), 883–889  mathnet  crossref  elib; V. V. Shenmaier, “Complexity and approximation of finding the longest vector sum”, Comput. Math. Math. Phys., 58:6 (2018), 850–857  crossref  isi
  • Труды Института математики и механики УрО РАН
    Просмотров:
    Эта страница:166
    Полный текст:38
    Литература:23
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020