А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62; J. Appl. Industr. Math., 9:4 (2015), 497

Дискретный анализ и исследование операций

RUS ENG

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

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

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

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

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

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

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

Дискретный анализ и исследование операций, 2015, том 22, выпуск 4, страницы 50–62
DOI: https://doi.org/10.17377/daio.2015.22.463 (Mi da824)

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

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

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

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

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

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

PDF

HTML

DOI: https://doi.org/10.17377/daio.2015.22.463

Аннотация: Рассматривается евклидова NP-трудная в сильном смысле задача разбиения конечного множества векторов на два кластера заданных размеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров неизвестен и определяется как среднее значение по всем векторам, образующим этот кластер. Центр другого кластера задан в начале координат. Показано, что в случае фиксированной размерности пространства задача разрешима за полиномиальное время. Для случая фиксированной размерности пространства и целочисленных компонент векторов обоснован точный псевдополиномиальный алгоритм. Библиогр. 27.

Ключевые слова: разбиение, множество векторов, квадраты евклидовых расстояний, NP-трудность, точный псевдополиномиальный алгоритм.

Статья поступила: 16.09.2014
Переработанный вариант: 22.02.2015

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2015, Volume 9, Issue 4, Pages 497–502
DOI: https://doi.org/10.1134/S1990478915040067

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

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

УДК: 519.16+519.85

Образец цитирования: А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62; J. Appl. Industr. Math., 9:4 (2015), 497–502

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

\RBibitem{KelKha15}

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

\paper Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов

\jour Дискретн. анализ и исслед. опер.

\yr 2015

\vol 22

\issue 4

\pages 50--62

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

\crossref{https://doi.org/10.17377/daio.2015.22.463}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3467235}

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

\transl

\jour J. Appl. Industr. Math.

\yr 2015

\vol 9

\issue 4

\pages 497--502

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

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

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

https://www.mathnet.ru/rus/da/v22/i4/p50

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

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. V. Kel'manov, V. I. Khandeev, A. V. Panasenko, “Exact Algorithms of Search For a Cluster of the Largest Size in Two Integer 2-Clustering Problems”, Numer. Anal. Appl., 12:2 (2019), 105–115
Alexander Kel'manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin, Communications in Computer and Information Science, 974, Optimization and Applications, 2019, 131
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, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 323–333
Alexander Kel'manov, Vladimir Khandeev, Anna Panasenko, Lecture Notes in Computer Science, 11179, Analysis of Images, Social Networks and Texts, 2018, 294
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 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
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
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 2017, № 1, 80–90 ; 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
А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 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. 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), 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), IEEE, 2017, 94–96
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, ed. D. Ignatov, M. Khachay, V. Labunets, N. Loukachevitch, S. Nikolenko, A. Panchenko, A. Savchenko, K. Vorontsov, Springler, 2017, 51–57
А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340 ; 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
А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$ -кластеризации”, Дискретн. анализ и исслед. опер., 23:3 (2016), 21–34 ; 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
Alexander Kel'manov, Anna Motkova, Lecture Notes in Computer Science, 9869, Discrete Optimization and Operations Research, 2016, 182
А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 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

Дискретный анализ и исследование операций

Статистика просмотров:
Страница аннотации:	379
PDF полного текста:	93
Список литературы:	72
Первая страница:	5

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

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

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

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

Логотипы