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

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

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



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






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


Дискретн. анализ и исслед. опер., 2011, том 18, номер 1, страницы 61–69 (Mi da638)  

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

Приближённый алгоритм решения одной задачи поиска подмножества векторов

А. В. Кельмановab, С. М. Романченкоb

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

Аннотация: Одна из проблем анализа данных сводится к решению NP-трудной экстремальной задачи поиска в множестве векторов евклидова пространства подмножества, имеющего заданную мощность и включающего векторы, “близкие” между собой по критерию минимума суммы квадратов расстояний. В работе обоснован полиномиальный 2-приближённый алгоритм решения этой задачи. Библиогр. 3.

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2012, 6:1, 90–96

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

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

Образец цитирования: А. В. Кельманов, С. М. Романченко, “Приближённый алгоритм решения одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 18:1 (2011), 61–69; J. Appl. Industr. Math., 6:1 (2012), 90–96

Цитирование в формате AMSBIB
\RBibitem{KelRom11}
\by А.~В.~Кельманов, С.~М.~Романченко
\paper Приближ\"енный алгоритм решения одной задачи поиска подмножества векторов
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 1
\pages 61--69
\mathnet{http://mi.mathnet.ru/da638}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2847829}
\zmath{https://zbmath.org/?q=an:1249.90189}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 1
\pages 90--96
\crossref{https://doi.org/10.1134/S1990478912010097}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84857671357}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da638
  • http://mi.mathnet.ru/rus/da/v18/i1/p61

    ОТПРАВИТЬ: 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. А. В. Кельманов, С. М. Романченко, “Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа”, Автомат. и телемех., 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
    2. В. В. Шенмайер, “Аппроксимационная схема для одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 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
    3. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Приближённые алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Дискретн. анализ и исслед. опер., 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
    4. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 53:1 (2013), 143–153  mathnet  crossref  elib
    5. И. И. Еремин, Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “$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
    6. А. В. Кельманов, С. А. Хамидуллин, “Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности”, Дискретн. анализ и исслед. опер., 21:1 (2014), 53–66  mathnet  mathscinet; A. V. Kelmanov, S. A. Khamidullin, “Approximation algorithm for one problem of partitioning a sequence”, J. Appl. Industr. Math., 8:2 (2014), 236–244  crossref
    7. А. Е. Галашов, А. В. Кельманов, “$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
    8. А. В. Кельманов, С. М. Романченко, “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
    9. Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 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
    10. А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 55:6 (2015), 1076–1085  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, S. A. Khamidullin, “An approximation polynomial-time algorithm for a sequence bi-clustering problem”, Comput. Math. Math. Phys., 55:6 (2015), 1068–1076  crossref  isi  elib
    11. А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 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
    12. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    13. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Аппроксимационная схема для задачи поиска подпоследовательности”, Сиб. журн. вычисл. матем., 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
    14. 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
    15. 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
    16. Kel'manov A., Motkova A., “An Approximation Polynomial-Time Algorithm For a Cardinality-Weighted 2-Clustering Problem”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 94–96  crossref  isi
    17. 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:335
    Полный текст:88
    Литература:34
    Первая стр.:7
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019