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

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

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



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






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


Дискретн. анализ и исслед. опер., 2009, том 16, номер 6, страницы 68–73 (Mi da595)  

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

О сложности задачи выбора подмножества векторов максимальной суммарной длины

А. В. Пяткинab

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

Аннотация: Рассматривается задача выбора подмножества векторов максимальной суммарной длины. В случае фиксированной размерности пространства эта задача является полиномиально разрешимой. Доказана NP-полнота задачи при нефиксированной размерности пространства. Библиогр. 6.

Ключевые слова: cуммирование векторов, сложность, NP-полнота.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2010, 4:4, 549–552

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

УДК: 519.2+621.391
Статья поступила: 04.08.2009

Образец цитирования: А. В. Пяткин, “О сложности задачи выбора подмножества векторов максимальной суммарной длины”, Дискретн. анализ и исслед. опер., 16:6 (2009), 68–73; J. Appl. Industr. Math., 4:4 (2010), 549–552

Цитирование в формате AMSBIB
\RBibitem{Pya09}
\by А.~В.~Пяткин
\paper О сложности задачи выбора подмножества векторов максимальной суммарной длины
\jour Дискретн. анализ и исслед. опер.
\yr 2009
\vol 16
\issue 6
\pages 68--73
\mathnet{http://mi.mathnet.ru/da595}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2649143}
\zmath{https://zbmath.org/?q=an:1249.68083}
\elib{http://elibrary.ru/item.asp?id=13008194}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 4
\pages 549--552
\crossref{https://doi.org/10.1134/S1990478910040095}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-78650071243}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da595
  • http://mi.mathnet.ru/rus/da/v16/i6/p68

    ОТПРАВИТЬ: 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. А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 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
    2. В. В. Шенмайер, “Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 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
    3. В. В. Шенмайер, “Аппроксимируемость задачи о подмножестве векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 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
    4. В. В. Шенмайер, “Сложность и аппроксимация задачи о длиннейшем суммарном векторе”, Ж. вычисл. матем. и матем. физ., 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:285
    Полный текст:65
    Литература:24
    Первая стр.:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019