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

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

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



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






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


Дискретн. анализ и исслед. опер., 2016, том 23, номер 4, страницы 102–115 (Mi da859)  

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

Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного

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

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

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

Ключевые слова: вычислительная геометрия, поиск подмножества векторов, евклидово пространство, диаграммa Вороного, полиномиальный алгоритм.

Финансовая поддержка Номер гранта
Российский научный фонд 16-11-10041
Исследование выполнено при финансовой поддержке Российского научного фонда (проект 16-11-10041).


DOI: https://doi.org/10.17377/daio.2016.23.526

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2016, 10:4, 560–566

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

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

Образец цитирования: В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 23:4 (2016), 102–115; J. Appl. Industr. Math., 10:4 (2016), 560–566

Цитирование в формате AMSBIB
\RBibitem{She16}
\by В.~В.~Шенмайер
\paper Решение некоторых задач поиска подмножества векторов с~использованием диаграмм Вороного
\jour Дискретн. анализ и исслед. опер.
\yr 2016
\vol 23
\issue 4
\pages 102--115
\mathnet{http://mi.mathnet.ru/da859}
\crossref{https://doi.org/10.17377/daio.2016.23.526}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3581886}
\elib{http://elibrary.ru/item.asp?id=27349045}
\transl
\jour J. Appl. Industr. Math.
\yr 2016
\vol 10
\issue 4
\pages 560--566
\crossref{https://doi.org/10.1134/S199047891604013X}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84996487016}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da859
  • http://mi.mathnet.ru/rus/da/v23/i4/p102

    ОТПРАВИТЬ: 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. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    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. 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
    4. 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
    5. A. Kel'manov, V. Khandeev, “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
    6. В. В. Шенмайер, “Аппроксимируемость задачи о подмножестве векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 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
    7. В. В. Шенмайер, “Сложность и аппроксимация задачи о длиннейшем суммарном векторе”, Ж. вычисл. матем. и матем. физ., 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
    8. 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:130
    Полный текст:42
    Литература:17
    Первая стр.:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019