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

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

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



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






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


Дискретн. анализ и исслед. опер., 2012, том 19, номер 2, страницы 92–100 (Mi da685)  

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

Аппроксимационная схема для одной задачи поиска подмножества векторов

В. В. Шенмайер

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

Аннотация: Рассматривается следующая задача кластеризации: среди заданного множества векторов найти подмножество мощности $k$, обладающее минимальным квадратичным отклонением от своего среднего. Расстояния между векторами определяются евклидовой метрикой. Предлагается аппроксимационная схема (PTAS), позволяющая решать данную задачу с произвольной относительной погрешностью $\varepsilon$ за время $O(n^{2/\varepsilon+1}(9/\varepsilon)^{3/\varepsilon}d)$, где $n$ – число векторов в исходном множестве, $d$ – размерность пространства. Ил. 1, библиогр. 4.

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

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

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

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

Тип публикации: Статья
УДК: 519.176
Статья поступила: 15.06.2011
Переработанный вариант: 08.09.2011

Образец цитирования: В. В. Шенмайер, “Аппроксимационная схема для одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 19:2 (2012), 92–100; J. Appl. Industr. Math., 6:3 (2012), 381–386

Цитирование в формате AMSBIB
\RBibitem{She12}
\by В.~В.~Шенмайер
\paper Аппроксимационная схема для одной задачи поиска подмножества векторов
\jour Дискретн. анализ и исслед. опер.
\yr 2012
\vol 19
\issue 2
\pages 92--100
\mathnet{http://mi.mathnet.ru/da685}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2978615}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 3
\pages 381--386
\crossref{https://doi.org/10.1134/S1990478912030131}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da685
  • http://mi.mathnet.ru/rus/da/v19/i2/p92

    ОТПРАВИТЬ: 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. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 53:1 (2013), 143–153  mathnet  crossref  elib
    2. А. Е. Галашов, А. В. Кельманов, “$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
    3. А. В. Кельманов, С. М. Романченко, “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
    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. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 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
    6. А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 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
    7. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 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
    8. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Аппроксимационная схема для задачи поиска подпоследовательности”, Сиб. журн. вычисл. матем., 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
    9. A. Ageev, A. Kel'manov, A. Pyatkin, S. Khamidullin, V. Shenmaier, “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
    10. A. Kel'manov, “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
    11. 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), IEEE, 2017, 94–96  crossref  isi
    12. 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
    13. 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, ed. Khachay M. Kochetov Y. Pardalos P., Springer International Publishing Ag, 2019, 541–551  crossref  zmath  isi  scopus
    14. Panasenko A., “a Ptas For One Cardinality-Weighted 2-Clustering Problem”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, ed. Khachay M. Kochetov Y. Pardalos P., Springer International Publishing Ag, 2019, 581–592  crossref  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:267
    Полный текст:66
    Литература:29
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020