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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 2, 2007, том 14, номер 1, страницы 32–42 (Mi da54)  

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

Задача отыскания подмножества векторов с максимальным суммарным весом

А. Е. Бабурин, Э. Х. Гимади, Н. И. Глебов, А. В. Пяткин

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

Аннотация: Доказана NP-трудность дискретных оптимизационных задач, связанных с выбором из конечного семейства векторов в евклидовом пространстве подмножества векторов с максимальной нормой суммы. Предложены приближённые алгоритмы и получены оценки для относительной погрешности и временно́й сложности. В случае фиксированной размерности пространства построена полиномиальная аппроксимационная схема. Выделен подкласс задач, для которых за псевдополиномиальное время отыскивается точное решение. Полученные результаты могут быть использованы для решения задачи выбора фиксированного числа фрагментов в числовой последовательности квазипериодически повторяющегося фрагмента при заданном числе повторов.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2008, 2:1, 32–38

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

УДК: 519.854
Статья поступила: 07.12.2006
Переработанный вариант: 16.05.2007

Образец цитирования: А. Е. Бабурин, Э. Х. Гимади, Н. И. Глебов, А. В. Пяткин, “Задача отыскания подмножества векторов с максимальным суммарным весом”, Дискретн. анализ и исслед. опер., сер. 2, 14:1 (2007), 32–42; J. Appl. Industr. Math., 2:1 (2008), 32–38

Цитирование в формате AMSBIB
\RBibitem{BabGimGle07}
\by А.~Е.~Бабурин, Э.~Х.~Гимади, Н.~И.~Глебов, А.~В.~Пяткин
\paper Задача отыскания подмножества векторов с~максимальным суммарным весом
\jour Дискретн. анализ и исслед. опер., сер.~2
\yr 2007
\vol 14
\issue 1
\pages 32--42
\mathnet{http://mi.mathnet.ru/da54}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2392668}
\zmath{https://zbmath.org/?q=an:1249.90211}
\transl
\jour J. Appl. Industr. Math.
\yr 2008
\vol 2
\issue 1
\pages 32--38
\crossref{https://doi.org/10.1007/s11754-008-1004-3}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-41749104288}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da54
  • http://mi.mathnet.ru/rus/da/v14/s2/i1/p32

    ОТПРАВИТЬ: 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. Э. Х. Гимади, Ю. В. Глазков, И. А. Рыков, “О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 15:4 (2008), 30–43  mathnet  mathscinet  zmath; E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “The vector subset problem with integer coordinates in Euclidean space with the maximum sum”, J. Appl. Industr. Math., 3:3 (2009), 343–352  crossref
    2. А. В. Кельманов, А. В. Пяткин, “Об одном варианте задачи выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 15:5 (2008), 20–34  mathnet  mathscinet  zmath; A. V. Kel'manov, A. V. Pyatkin, “On one variant of the vectors subset choice problem”, J. Appl. Industr. Math., 3:4 (2009), 447–455  crossref
    3. А. В. Кельманов, “Проблема off-line обнаружения квазипериодически повторяющегося фрагмента в числовой последовательности”, Тр. ИММ УрО РАН, 14, № 2, 2008, 81–88  mathnet  zmath  elib; A. V. Kel'manov, “Off-line detection of a quasi-periodically recurring fragment in a numerical sequence”, Proc. Steklov Inst. Math. (Suppl.), 263, suppl. 2 (2008), S84–S92  crossref  isi
    4. Kel'manov A.V., Pyatkin A.V., “On the complexity of a search for a subset of “similar” vectors”, Doklady Mathematics, 78:1 (2008), 574–575  crossref  mathscinet  zmath  isi  scopus
    5. А. В. Пяткин, “О сложности задачи выбора подмножества векторов максимальной суммарной длины”, Дискретн. анализ и исслед. опер., 16:6 (2009), 68–73  mathnet  mathscinet  zmath  elib; A. V. Pyatkin, “On the complexity of the maximum sum length vectors subset choice problem”, J. Appl. Industr. Math., 4:4 (2010), 549–552  crossref
    6. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач поиска подмножеств векторов и кластерного анализа”, Ж. вычисл. матем. и матем. физ., 49:11 (2009), 2059–2065  mathnet  mathscinet; 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  crossref  isi
    7. А. В. Кельманов, А. В. Пяткин, “NP-полнота некоторых задач выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 17:5 (2010), 37–45  mathnet  mathscinet  zmath; 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  crossref
    8. А. В. Кельманов, “$NP$-полнота некоторых задач поиска подмножеств векторов”, Тр. ИММ УрО РАН, 16, № 3, 2010, 121–129  mathnet  elib
    9. А. В. Кельманов, “О сложности некоторых задач анализа данных”, Ж. вычисл. матем. и матем. физ., 50:11 (2010), 2045–2051  mathnet  adsnasa; A. V. Kel'manov, “On the complexity of some data analysis problems”, Comput. Math. Math. Phys., 50:11 (2010), 1941–1947  crossref  isi
    10. А. В. Долгушев, А. В. Кельманов, “Приближëнный алгоритм решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 18:2 (2011), 29–40  mathnet  mathscinet  zmath; A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for one problem of cluster analysis”, J. Appl. Industr. Math., 5:4 (2011), 551–558  crossref
    11. Э. Х. Гимади, И. А. Рыков, “Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы”, Дискретн. анализ и исслед. опер., 22:3 (2015), 5–17  mathnet  crossref  mathscinet  elib; E. Kh. Gimadi, I. A. Rykov, “A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum”, J. Appl. Industr. Math., 9:3 (2015), 351–357  crossref
    12. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  crossref
    13. А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 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
    14. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
    15. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    16. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $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
    17. А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836  mathnet  crossref  elib; 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  crossref  isi
    18. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 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
    19. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 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
    20. В. В. Шенмайер, “Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 24:4 (2017), 111–129  mathnet  crossref  elib; V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Industr. Math., 11:4 (2017), 584–593  crossref
    21. 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  crossref  isi
    22. 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, eds. Ignatov D., Khachay M., Labunets V., Loukachevitch N., Nikolenko S., Panchenko A., Savchenko A., Vor, Springer International Publishing Ag, 2017, 51–57  crossref  isi  scopus
    23. В. В. Шенмайер, “Аппроксимируемость задачи о подмножестве векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 25:4 (2018), 131–148  mathnet  crossref  elib; V. V. Shenmaier, “Approximability of the problem of finding a vector subset with the longest sum”, J. Appl. Industr. Math., 12:4 (2018), 749–758  crossref
    24. В. В. Шенмайер, “Сложность и аппроксимация задачи о длиннейшем суммарном векторе”, Ж. вычисл. матем. и матем. физ., 58:6 (2018), 883–889  mathnet  crossref  elib; V. V. Shenmaier, “Complexity and approximation of finding the longest vector sum”, Comput. Math. Math. Phys., 58:6 (2018), 850–857  crossref  isi
    25. А. В. Кельманов, А. В. Пяткин, В. И. Хандеев, “Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость”, Тр. ИММ УрО РАН, 25, № 4, 2019, 69–78  mathnet  crossref  elib
    26. Kel'manov A.V., Pyatkin A.V., Khandeev V.I., “Np-Hardness of Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem With Constraints on the Cluster Sizes”, Dokl. Math., 100:3 (2019), 545–548  crossref  mathscinet  zmath  isi  scopus
    27. 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  mathnet  crossref  mathscinet  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:635
    Полный текст:180
    Литература:55
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020