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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2015, том 55, номер 2, страницы 335–344 (Mi zvmmf10162)  

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

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

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

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

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

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

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


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

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2015, 55:2, 330–339

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

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

Образец цитирования: А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344; Comput. Math. Math. Phys., 55:2 (2015), 330–339

Цитирование в формате AMSBIB
\RBibitem{KelKha15}
\by А.~В.~Кельманов, В.~И.~Хандеев
\paper Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов
\jour Ж. вычисл. матем. и матем. физ.
\yr 2015
\vol 55
\issue 2
\pages 335--344
\mathnet{http://mi.mathnet.ru/zvmmf10162}
\crossref{https://doi.org/10.7868/S0044466915020131}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3317887}
\elib{https://elibrary.ru/item.asp?id=22908475}
\transl
\jour Comput. Math. Math. Phys.
\yr 2015
\vol 55
\issue 2
\pages 330--339
\crossref{https://doi.org/10.1134/S096554251502013X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000350801800017}
\elib{https://elibrary.ru/item.asp?id=24011263}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84924119914}


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

    ОТПРАВИТЬ: 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. 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, 94–96  crossref  isi
    2. Э. Х. Гимади, И. А. Рыков, “Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы”, Дискретн. анализ и исслед. опер., 22:3 (2015), 5–17  mathnet  crossref  mathscinet  elib; E. Kh. Gimadi, I. A. Rykov, “A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum”, J. Appl. Industr. Math., 9:3 (2015), 351–357  crossref
    3. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  crossref
    4. А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 21, № 3, 2015, 100–109  mathnet  mathscinet  elib; 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, suppl. 1 (2016), 47–56  crossref  isi
    5. В. М. Неделько, “К вопросу об эффективности бустинга в задаче классификации”, Вестн. НГУ. Сер. матем., мех., информ., 15:2 (2015), 72–89  mathnet  crossref
    6. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
    7. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    8. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $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
    9. L. I. Rubanov, A. V. Seliverstov, O. A. Zverkov, V. A. Lyubetsky, “A method for identification of highly conserved elements and evolutionary analysis of superphylum Alveolata”, BMC Bioinformatics, 17 (2016), 385  crossref  isi  elib  scopus
    10. 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
    11. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 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
    12. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 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
    13. 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, K. , Springer, 2017, 51–57  crossref  isi
    14. 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
    15. 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
    16. 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
    17. А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 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
    18. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 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
    19. А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации”, Сиб. журн. вычисл. матем., 22:2 (2019), 121–136  mathnet  crossref  elib; A. V. Kel'manov, A. V. Panasenko, V. I. Khandeev, “Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems”, Num. Anal. Appl., 12:2 (2019), 105–115  crossref  isi
    20. А. В. Кельманов, А. В. Пяткин, В. И. Хандеев, “Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость”, Тр. ИММ УрО РАН, 25, № 4, 2019, 69–78  mathnet  crossref  elib
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:222
    Полный текст:38
    Литература:38
    Первая стр.:19
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020