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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2016, том 56, номер 10, страницы 1831–1836 (Mi zvmmf10476)  

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

А. В. Еремеевab, А. В. Кельмановac, А. В. Пяткинac

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

Аннотация: Анализируется статус вычислительной сложности нескольких известных дискретных экстремальных задач с измененным направлением оптимизации, а именно: c $\max$ на $\min$. Рассматриваются евклидовы задачи поиска подмножества в конечном множестве точек (векторов). В этих задачах целевые функции зависят либо только от нормы суммы элементов подмножества, либо от этой нормы и мощности искомого подмножества. Доказано, что если размерность пространства является частью входа, то все рассмотренные задачи $\mathrm{NP}$-трудны в сильном смысле. Установлено, что при фиксированной размерности пространства все задачи $\mathrm{NP}$-трудны даже в двумерном случае (на плоскости) и для них не существует приближенных алгоритмов с гарантированной оценкой точности, если $\mathrm{P\ne NP}$. Показано, что если координаты входных точек целочисленны, то все задачи разрешимы за псевдополиномиальное время в случае, когда размерность пространства фиксирована. Библ. 17.

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462_а
15-01-00785_а
15-01-00976_а
Работа выполнена при финансовой поддержке РФФИ (коды проектов 15-01-00462, 15-01-00785, 15-01-00976).


DOI: https://doi.org/10.7868/S0044466916100082

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2016, 56:10, 1813–1817

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

Тип публикации: Статья
УДК: 519.7
Поступила в редакцию: 20.11.2015

Образец цитирования: А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836; Comput. Math. Math. Phys., 56:10 (2016), 1813–1817

Цитирование в формате AMSBIB
\RBibitem{EreKelPya16}
\by А.~В.~Еремеев, А.~В.~Кельманов, А.~В.~Пяткин
\paper О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования
\jour Ж. вычисл. матем. и матем. физ.
\yr 2016
\vol 56
\issue 10
\pages 1831--1836
\mathnet{http://mi.mathnet.ru/zvmmf10476}
\crossref{https://doi.org/10.7868/S0044466916100082}
\elib{http://elibrary.ru/item.asp?id=26665214}
\transl
\jour Comput. Math. Math. Phys.
\yr 2016
\vol 56
\issue 10
\pages 1813--1817
\crossref{https://doi.org/10.1134/S0965542516100080}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000386769200014}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84992380023}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf10476
  • http://mi.mathnet.ru/rus/zvmmf/v56/i10/p1831

    ОТПРАВИТЬ: 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
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:118
    Полный текст:4
    Литература:30
    Первая стр.:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020