|
|
Дискретн. анализ и исслед. опер., 2008, том 15, номер 5, страницы 20–34
(Mi da547)
|
 |
|
 |
Эта публикация цитируется в 17 научных статьях (всего в 17 статьях)
Об одном варианте задачи выбора подмножества векторов
А. В. Кельманов, А. В. Пяткин
Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Доказана NP-полнота задачи выбора подмножества “похожих” векторов, к которой сводится один из вариантов проблемы апостериорного (off-line) помехоустойчивого обнаружения в числовой последовательности неизвестного повторяющегося вектора в случае, когда помеха аддитивна. Обоснован приближённый полиномиальный алгоритм решения этой задачи с гарантированной оценкой точности в случае фиксированной размерности пространства. Библиогр. 13.
Ключевые слова:
числовая векторная последовательность, апостериорная обработка, повторяющийся вектор, оптимальное помехоустойчивое обнаружение, сложность, NP-полнота, приближённый алгоритм.
 Полный текст:
PDF файл (288 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2009, 3:4, 447–455
Реферативные базы данных:
  
УДК:
519.2+621.391
Статья поступила: 01.04.2008
Образец цитирования:
А. В. Кельманов, А. В. Пяткин, “Об одном варианте задачи выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 15:5 (2008), 20–34; J. Appl. Industr. Math., 3:4 (2009), 447–455
Цитирование в формате AMSBIB
\RBibitem{KelPya08}
\by А.~В.~Кельманов, А.~В.~Пяткин
\paper Об одном варианте задачи выбора подмножества векторов
\jour Дискретн. анализ и исслед. опер.
\yr 2008
\vol 15
\issue 5
\pages 20--34
\mathnet{http://mi.mathnet.ru/da547}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2543152}
\zmath{https://zbmath.org/?q=an:1249.90343}
\transl
\jour J. Appl. Industr. Math.
\yr 2009
\vol 3
\issue 4
\pages 447--455
\crossref{https://doi.org/10.1134/S1990478909040036}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77749309541}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da547 http://mi.mathnet.ru/rus/da/v15/i5/p20
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Э. Х. Гимади, А. В. Пяткин, И. А. Рыков, “О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности”, Дискретн. анализ и исслед. опер., 15:6 (2008), 11–19
 ; E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension”, J. Appl. Industr. Math., 4:1 (2010), 48–53 -
А. В. Пяткин, “О сложности задачи выбора подмножества векторов максимальной суммарной длины”, Дискретн. анализ и исслед. опер., 16:6 (2009), 68–73
 ; A. V. Pyatkin, “On the complexity of the maximum sum length vectors subset choice problem”, J. Appl. Industr. Math., 4:4 (2010), 549–552 -
А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач поиска подмножеств векторов и кластерного анализа”, Ж. вычисл. матем. и матем. физ., 49:11 (2009), 2059–2065 ; A. V. Kel'manov, A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis”, Comput. Math. Math. Phys., 49:11 (2009), 1966–1971
 -
А. В. Кельманов, А. В. Пяткин, “NP-полнота некоторых задач выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 17:5 (2010), 37–45 ; A. V. Kel'manov, A. V. Pyatkin, “NP-completeness of some problems of a vectors subset choice”, J. Appl. Industr. Math., 5:3 (2011), 352–357
-
А. В. Кельманов, “$NP$-полнота некоторых задач поиска подмножеств векторов”, Тр. ИММ УрО РАН, 16, № 3, 2010, 121–129
-
А. В. Кельманов, “О сложности некоторых задач анализа данных”, Ж. вычисл. матем. и матем. физ., 50:11 (2010), 2045–2051
 ; A. V. Kel'manov, “On the complexity of some data analysis problems”, Comput. Math. Math. Phys., 50:11 (2010), 1941–1947 -
А. В. Кельманов, “О сложности некоторых задач кластерного анализа”, Ж. вычисл. матем. и матем. физ., 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
-
А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач кластерного анализа векторных последовательностей”, Дискретн. анализ и исслед. опер., 20:2 (2013), 47–57 ; A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some vector sequence clustering problems”, J. Appl. Industr. Math., 7:3 (2013), 363–369
-
А. В. Кельманов, В. И. Хандеев, “Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 20:4 (2013), 36–45 ; A. V. Kelmanov, V. I. Khandeev, “A $2$-approximation polynomial algorithm for one clustering problem”, J. Appl. Industr. Math., 7:4 (2013), 515–521
-
А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 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, suppl. 1 (2016), 47–56
-
А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
-
А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836 ; A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Comput. Math. Math. Phys., 56:10 (2016), 1813–1817
-
В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 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
-
Kel'manov A. Khandeev V., “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
-
Eremeev A.V. Kel'manov A.V. Pyatkin A.V., “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. Ignatov D. Khachay M. Labunets V. Loukachevitch N. Nikolenko S. Panchenko A. Savchenko A. Vorontsov K., Springer International Publishing Ag, 2017, 51–57
-
Kel'manov A.V., Khandeev V.I., “on Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line”, Dokl. Math., 100:1 (2019), 339–342
-
Kel'manov V A. Panasenko V A. Khandeev I V., “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
|
| Просмотров: |
| Эта страница: | 465 | | Полный текст: | 113 | | Литература: | 45 | | Первая стр.: | 10 |
|
Пользовательское соглашение