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

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

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



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






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


Дискретн. анализ и исслед. опер., 2014, том 21, номер 3, страницы 41–52 (Mi da774)  

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

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

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

a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

Аннотация: Рассматривается NP-трудная в сильном смысле задача поиска в конечном множестве векторов евклидова пространства подмножества заданной мощности, доставляющего минимум сумме квадратов расстояний от элементов подмножества до его центра. Центр искомого подмножества определяется как cреднее значение вектора по всем элементам подмножества. Доказано, что если P$\neq$NP, то для общего случая этой задачи не существует полностью полиномиальной приближённой схемы (FPTAS). Для специального случая этой задачи, когда размерность пространства фиксирована, такая схема обоснована. Библиогр. 12.

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2014, 8:3, 329–336

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

Тип публикации: Статья
УДК: 519.16+519.85
Статья поступила: 11.11.2013
Переработанный вариант: 29.01.2014

Образец цитирования: А. В. Кельманов, С. М. Романченко, “FPTAS для одной задачи поиска подмножества векторов”, Дискретн. анализ и исслед. опер., 21:3 (2014), 41–52; J. Appl. Industr. Math., 8:3 (2014), 329–336

Цитирование в формате AMSBIB
\RBibitem{KelRom14}
\by А.~В.~Кельманов, С.~М.~Романченко
\paper FPTAS для одной задачи поиска подмножества векторов
\jour Дискретн. анализ и исслед. опер.
\yr 2014
\vol 21
\issue 3
\pages 41--52
\mathnet{http://mi.mathnet.ru/da774}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3242100}
\transl
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 3
\pages 329--336
\crossref{https://doi.org/10.1134/S1990478914030041}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da774
  • http://mi.mathnet.ru/rus/da/v21/i3/p41

    ОТПРАВИТЬ: 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. Zverkov O.A., Seliverstov A.V., Lyubetsky V.A., “a Database of Plastid Protein Families From Red Algae and Apicomplexa and Expression Regulation of the Moeb Gene”, Biomed Res. Int., 2015, 510598  crossref  isi  scopus
    2. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
    3. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  crossref
    4. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 22, № 3, 2016, 144–152  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96  crossref  isi
    5. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$-кластеризации”, Дискретн. анализ и исслед. опер., 23:3 (2016), 21–34  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, A. V. Motkova, “Exact pseudopolinomial algorithms for a balanced $2$-clustering problem”, J. Appl. Industr. Math., 10:3 (2016), 349–355  crossref
    6. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 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
    7. А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 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
    8. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    9. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Аппроксимационная схема для задачи поиска подпоследовательности”, Сиб. журн. вычисл. матем., 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
    10. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры”, Ж. вычисл. матем. и матем. физ., 57:8 (2017), 1392–1400  mathnet  crossref  elib; A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “Approximation algorithm for the problem of partitioning a sequence into clusters”, Comput. Math. Math. Phys., 57:8 (2017), 1376–1383  crossref  isi
    11. 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
    12. 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
    13. 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
    14. А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142  mathnet  crossref  elib; A. V. Kel'manov, A. V. Motkova, “Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center”, Comput. Math. Math. Phys., 58:1 (2018), 130–136  crossref  isi
    15. A. Kel'manov, A. Motkova, V. Shenmaier, “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, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 323–333  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:276
    Полный текст:69
    Литература:49
    Первая стр.:32
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019