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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2016, том 56, номер 2, страницы 332–340 (Mi zvmmf10348)  

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

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

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

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

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

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

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


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

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2016, 56:2, 334–341

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

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

Образец цитирования: А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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{http://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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000373669000014}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84962736649}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf10348
  • http://mi.mathnet.ru/rus/zvmmf/v56/i2/p332

    ОТПРАВИТЬ: 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. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    2. 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  crossref  mathscinet  zmath  isi  scopus
    3. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    4. 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  crossref  isi
    5. 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  crossref  isi
    6. 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  crossref  isi
    7. 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  crossref  isi
    8. 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  crossref  isi  scopus
    9. 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  crossref  isi  scopus
    10. А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 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
    11. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178  mathnet  crossref  elib; 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  crossref  isi
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:172
    Полный текст:17
    Литература:49
    Первая стр.:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019