А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340; Comput. Math. Math. Phys., 56:2 (2016), 334

Журнал вычислительной математики и математической физики

RUS ENG

ЖУРНАЛЫ ПЕРСОНАЛИИ ОРГАНИЗАЦИИ КОНФЕРЕНЦИИ СЕМИНАРЫ ВИДЕОТЕКА ПАКЕТ AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	Общая информация
	Последний выпуск
	Архив
	Импакт-фактор

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

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

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

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

Журнал вычислительной математики и математической физики, 2016, том 56, номер 2, страницы 332–340
DOI: https://doi.org/10.7868/S0044466916020113 (Mi zvmmf10348)

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

Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации

А. В. Кельманов^ab, В. И. Хандеев^ab

^a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т математики СО РАН
^b 630090 Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т

PDF полного текста (184 kB) Список цитирования (16)

Список литературы:

PDF

HTML

DOI: https://doi.org/10.7868/S0044466916020113

Аннотация: Рассматривается $\mathrm{NP}$-трудная в сильном смысле задача разбиения конечного множества точек евклидова пространства на два кластера заданных размеров по критерию минимума суммы по обоим кластерам сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров задан в желаемой (произвольной) точке пространства (без ограничения общности — в начале координат), а центр другого неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер. Установлено, что для этой задачи не существует полностью полиномиальной приближенной схемы, если $\mathrm{P\ne NP}$, и такая схема обоснована для случая, когда размерность пространства фиксирована. Библ. 29.

Ключевые слова: кластерный анализ, разбиение, евклидово пространство, минимум суммы квадратов расстояний, $\mathrm{NP}$-трудность, фиксированная размерность пространства, FPTAS.

Финансовая поддержка	Номер гранта
Российский фонд фундаментальных исследований	13-07-00070_а 15-01-00462_а
Работа выполнена при поддержке РФФИ (коды проектов 13-07-00070, 15-01-00462).

Поступила в редакцию: 02.03.2015

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2016, Volume 56, Issue 2, Pages 334–341
DOI: https://doi.org/10.1134/S0965542516020111

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

Тип публикации: Статья

УДК: 519.7

Образец цитирования: А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340; Comput. Math. Math. Phys., 56:2 (2016), 334–341

Цитирование в формате AMSBIB

\RBibitem{KelKha16}

\by А.~В.~Кельманов, В.~И.~Хандеев

\paper Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации

\jour Ж. вычисл. матем. и матем. физ.

\yr 2016

\vol 56

\issue 2

\pages 332--340

\mathnet{http://mi.mathnet.ru/zvmmf10348}

\crossref{https://doi.org/10.7868/S0044466916020113}

\elib{https://elibrary.ru/item.asp?id=25343620}

\transl

\jour Comput. Math. Math. Phys.

\yr 2016

\vol 56

\issue 2

\pages 334--341

\crossref{https://doi.org/10.1134/S0965542516020111}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000373669000014}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84962736649}

Образцы ссылок на эту страницу:

https://www.mathnet.ru/rus/zvmmf10348

https://www.mathnet.ru/rus/zvmmf/v56/i2/p332

Эта публикация цитируется в следующих 16 статьяx:

Vladimir Khandeev, Anna Panasenko, Communications in Computer and Information Science, 1275, Mathematical Optimization Theory and Operations Research, 2020, 30
A. Panasenko, “A PTAS for one cardinality-weighted 2-clustering problem”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, ed. M. Khachay, Y. Kochetov, P. Pardalos, Springer, 2019, 581–592
A. Kel'manov, S. Khamidullin, V. Khandeev, “A randomized algorithm for 2-partition of a sequence”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. VanDerAalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, Springer, 2018, 313–322
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. VanDerAalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 323–333
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142 ; 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
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178 ; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “A randomized algorithm for a sequence 2-clustering problem”, Comput. Math. Math. Phys., 58:12 (2018), 2078–2085
A. V. Kel'manov, A. V. Motkova, “Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem”, Pattern Recognit. Image Anal., 28:1 (2018), 17
A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, A. V. Pyatkin, “An Exact Algorithm of Searching for the Largest Cluster in an Integer-Valued Problem of 2-Partitioning a Sequence”, Pattern Recognit. Image Anal., 28:4 (2018), 703
А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170 ; 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
A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On complexity of searching a subset of vectors with shortest average under a cardinality restriction”, Analysis of Images, Social Networks and Texts, AIST 2016, Communications in Computer and Information Science, 661, eds. D. Ignatov, M. Khachay, V. Labunets, N. Loukachevitch, S. Nikolenko, A. Panchenko, A. Savchenko, et, Springler, 2017, 51–57
A. Kel'manov, “Efficient approximation algorithms for some NP-hard problems of partitioning a set and a sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, IEEE, 2017, 87–90
A. Kel'manov, V. Khandeev, “Some algorithms with guaranteed accuracy for 2-clustering problems with given center of one cluster”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, IEEE, 2017, 91–93
A. Kel'manov, A. Motkova, “An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, IEEE, 2017, 94–96
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40 ; 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
A. Kel'manov, A. Motkova, “A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem”, Discrete Optimization and Operations Research, Lecture Notes in Computer Science, 9869, ed. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, Springer Int Publishing Ag, 2016, 182–192
А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 21:3 (2015), 100–109 ; A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math. (Suppl.), 295:1 (2016), 47–56

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Журнал вычислительной математики и математической физики

Computational Mathematics and Mathematical Physics

Статистика просмотров:
Страница аннотации:	339
PDF полного текста:	61
Список литературы:	75
Первая страница:	10

Что такое QR-код?

Обратная связь:
math-net2025_03@mi-ras.ru

Пользовательское соглашение

Регистрация посетителей портала

Логотипы