|
|
Дискретн. анализ и исслед. опер., 2010, том 17, номер 5, страницы 37–45
(Mi da623)
|
 |
|
 |
Эта публикация цитируется в 24 научных статьях (всего в 24 статьях)
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{https://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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. В. Кельманов, С. М. Романченко, “Приближённый алгоритм решения одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 18:1 (2011), 61–69
 ; 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 -
А. В. Кельманов, “О сложности некоторых задач кластерного анализа”, Ж. вычисл. матем. и матем. физ., 51:11 (2011), 2106–2112 ; A. V. Kel'manov, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988
 -
А. В. Кельманов, С. М. Романченко, “Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа”, Автомат. и телемех., 2012, № 2, 156–162 ; 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
-
В. В. Шенмайер, “Аппроксимационная схема для одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 19:2 (2012), 92–100 ; V. V. Shenmaier, “Approximation scheme for one problem of a vector subset choice”, J. Appl. Industr. Math., 6:3 (2012), 381–386
-
А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Приближённые алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Дискретн. анализ и исслед. опер., 19:3 (2012), 27–38 ; 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
-
А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач выбора подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 52:12 (2012), 2284–2291
-
В. В. Шенмайер, “Задача о минимальном шаре, охватывающем $k$ точек”, Дискретн. анализ и исслед. опер., 20:1 (2013), 93–99 ; V. V. Shenmaier, “The smallest $k$-enclosing ball problem”, J. Appl. Industr. Math., 7:3 (2013), 444–448
-
А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 53:1 (2013), 143–153
 -
И. И. Еремин, Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “$2$-приближенный алгоритм поиска клики с минимальным весом вершин и ребер”, Тр. ИММ УрО РАН, 19, № 2, 2013, 134–143 ; 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
-
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
-
А. Е. Галашов, А. В. Кельманов, “$2$-приближенный алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов”, Автомат. и телемех., 2014, № 4, 5–19 ; 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
-
А. В. Кельманов, С. М. Романченко, “FPTAS для одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 21:3 (2014), 41–52 ; 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
-
Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112 ; 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
-
А. А. Агеев, А. В. Кельманов, А. В. Пяткин, “Cложность задачи о разрезе максимального веса в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 21:4 (2014), 3–11 ; 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
-
Shenmaier V., “Complexity and Approximation of the Smallest K-Enclosing Ball Problem”, Eur. J. Comb., 48:SI (2015), 81–87
-
А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
-
В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 23:4 (2016), 102–115 ; V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566
-
А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 20:1 (2017), 15–22 ; 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
-
А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 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
-
А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Аппроксимационная схема для задачи поиска подпоследовательности”, Сиб. журн. вычисл. матем., 20:4 (2017), 379–392 ; 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
-
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
-
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
-
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
-
Eremeev A.V., Kel'manov A.V., Kovalyov M.Y., Pyatkin A.V., “Maximum Diversity Problem With Squared Euclidean Distance”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, eds. Khachay M., Kochetov Y., Pardalos P., Springer International Publishing Ag, 2019, 541–551
|
| Просмотров: |
| Эта страница: | 528 | | Полный текст: | 162 | | Литература: | 54 | | Первая стр.: | 3 |
|
Пользовательское соглашение