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

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

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



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






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


Дискретн. анализ и исслед. опер., 2010, том 17, номер 5, страницы 37–45 (Mi da623)  

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

NP-полнота некоторых задач выбора подмножества векторов

А. В. Кельмановab, А. В. Пяткинab

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

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

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2011, 5:3, 352–357

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

Тип публикации: Статья
УДК: 519.2+621.391
Статья поступила: 12.04.2010
Переработанный вариант: 06.07.2010

Образец цитирования: А. В. Кельманов, А. В. Пяткин, “NP-полнота некоторых задач выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 17:5 (2010), 37–45; J. Appl. Industr. Math., 5:3 (2011), 352–357

Цитирование в формате AMSBIB
\RBibitem{KelPya10}
\by А.~В.~Кельманов, А.~В.~Пяткин
\paper NP-полнота некоторых задач выбора подмножества векторов
\jour Дискретн. анализ и исслед. опер.
\yr 2010
\vol 17
\issue 5
\pages 37--45
\mathnet{http://mi.mathnet.ru/da623}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2779350}
\zmath{https://zbmath.org/?q=an:1249.68080}
\transl
\jour J. Appl. Industr. Math.
\yr 2011
\vol 5
\issue 3
\pages 352--357
\crossref{https://doi.org/10.1134/S1990478911030069}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80052019433}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da623
  • http://mi.mathnet.ru/rus/da/v17/i5/p37

    ОТПРАВИТЬ: 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. А. В. Кельманов, С. М. Романченко, “Приближённый алгоритм решения одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 18:1 (2011), 61–69  mathnet  mathscinet  zmath; A. V. Kel'manov, S. M. Romanchenko, “The approximation algorithm for one problem of searching for subset of vectors”, J. Appl. Industr. Math., 6:1 (2012), 90–96  crossref
    2. А. В. Кельманов, “О сложности некоторых задач кластерного анализа”, Ж. вычисл. матем. и матем. физ., 51:11 (2011), 2106–2112  mathnet  mathscinet; A. V. Kel'manov, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988  crossref  isi
    3. А. В. Кельманов, С. М. Романченко, “Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа”, Автомат. и телемех., 2012, № 2, 156–162  mathnet; A. V. Kel'manov, S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems”, Autom. Remote Control, 73:2 (2012), 349–354  crossref  isi
    4. В. В. Шенмайер, “Аппроксимационная схема для одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 19:2 (2012), 92–100  mathnet  mathscinet; V. V. Shenmaier, “Approximation scheme for one problem of a vector subset choice”, J. Appl. Industr. Math., 6:3 (2012), 381–386  crossref
    5. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Приближённые алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Дискретн. анализ и исслед. опер., 19:3 (2012), 27–38  mathnet  mathscinet; A. V. Kel'manov, S. M. Romanchenko, S. A. Khamidullin, “Approximation algorithms for some NP-hard problems of searching a vectors subsequence”, J. Appl. Industr. Math., 6:4 (2012), 443–450  crossref
    6. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач выбора подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 52:12 (2012), 2284–2291  mathnet
    7. В. В. Шенмайер, “Задача о минимальном шаре, охватывающем $k$ точек”, Дискретн. анализ и исслед. опер., 20:1 (2013), 93–99  mathnet  mathscinet; V. V. Shenmaier, “The smallest $k$-enclosing ball problem”, J. Appl. Industr. Math., 7:3 (2013), 444–448  crossref
    8. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 53:1 (2013), 143–153  mathnet  crossref  elib
    9. И. И. Еремин, Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “$2$-приближенный алгоритм поиска клики с минимальным весом вершин и ребер”, Тр. ИММ УрО РАН, 19, № 2, 2013, 134–143  mathnet  mathscinet  elib; I. I. Eremin, E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “$2$-approximate algorithm for finding a clique with minimum weight of vertices and edges”, Proc. Steklov Inst. Math. (Suppl.), 284, suppl. 1 (2014), 87–95  crossref  isi
    10. Shenmaier V.V., “Computational Complexity and Approximation for a Generalization of the Euclidean Problem on the Chebyshev Center”, Dokl. Math., 87:3 (2013), 342–344  crossref  zmath  isi  elib  scopus
    11. А. Е. Галашов, А. В. Кельманов, “$2$-приближенный алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов”, Автомат. и телемех., 2014, № 4, 5–19  mathnet; A. E. Galashov, A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of the family of disjoint vector subsets”, Autom. Remote Control, 75:4 (2014), 595–606  crossref  isi
    12. А. В. Кельманов, С. М. Романченко, “FPTAS для одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 21:3 (2014), 41–52  mathnet  mathscinet; A. V. Kel'manov, S. M. Romanchenko, “FPTAS for solving a problem of search for a vector subset”, J. Appl. Industr. Math., 8:3 (2014), 329–336  crossref
    13. Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112  mathnet  mathscinet  elib; E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  crossref  isi
    14. А. А. Агеев, А. В. Кельманов, А. В. Пяткин, “Cложность задачи о разрезе максимального веса в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 21:4 (2014), 3–11  mathnet  mathscinet; A. A. Ageev, A. V. Kel'manov, A. V. Pyatkin, “Complexity of the Euclidean max cut problem”, J. Appl. Industr. Math., 8:4 (2014), 453–457  crossref
    15. Shenmaier V., “Complexity and Approximation of the Smallest K-Enclosing Ball Problem”, Eur. J. Comb., 48:SI (2015), 81–87  crossref  mathscinet  zmath  isi  scopus
    16. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
    17. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 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
    18. А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 20:1 (2017), 15–22  mathnet  crossref  mathscinet  elib; A. E. Galashov, A. V. Kel'manov, “On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets”, Num. Anal. Appl., 10:1 (2017), 11–16  crossref  isi
    19. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    20. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Аппроксимационная схема для задачи поиска подпоследовательности”, Сиб. журн. вычисл. матем., 20:4 (2017), 379–392  mathnet  crossref  elib; A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “An approximation scheme for a problem of finding a subsequence”, Num. Anal. Appl., 10:4 (2017), 313–323  crossref  isi
    21. Ageev A., Kel'manov A., Pyatkin A., Khamidullin S., Shenmaier V., “1/2-Approximation Polynomial-Time Algorithm For a Problem of Searching a Subset”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 8–12  crossref  isi
    22. Kel'manov A., “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), IEEE, 2017, 87–90  crossref  isi
    23. Kel'manov A. Motkova A. Shenmaier V., “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, ed. VanDerAalst W. Ignatov D. Khachay M. Kuznetsov S. Lempitsky V. Lomazova I. Loukachevitch N. Napoli A. Panchenko A. Pardalos P. Savchenko A. Wasserman S., Springer International Publishing Ag, 2018, 323–333  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:487
    Полный текст:144
    Литература:53
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019