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

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

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



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






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


Автомат. и телемех., 2014, выпуск 4, страницы 5–19 (Mi at7528)  

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

Задачи математического программирования

$2$-приближенный алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов

А. Е. Галашовa, А. В. Кельмановb

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

Аннотация: Рассматривается задача поиска в конечном множестве векторов евклидова пространства семейства непересекающихся подмножеств, имеющих заданные мощности. Критерием поиска является минимум суммы квадратов расстояний от элементов подмножеств до их центров. Центры подмножеств являются оптимизируемыми величинами и определяются как средние значения по элементам искомых подмножеств. Показано, что задача NP-трудна в сильном смысле. Предложен $2$-приближенный алгоритм решения задачи. При фиксированном числе искомых подмножеств алгоритм полиномиален.

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

Англоязычная версия:
Automation and Remote Control, 2014, 75:4, 595–606

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

Тип публикации: Статья
Статья представлена к публикации членом редколлегии: А. И. Кибзун

Поступила в редакцию: 14.11.2013

Образец цитирования: А. Е. Галашов, А. В. Кельманов, “$2$-приближенный алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов”, Автомат. и телемех., 2014, № 4, 5–19; Autom. Remote Control, 75:4 (2014), 595–606

Цитирование в формате AMSBIB
\RBibitem{GalKel14}
\by А.~Е.~Галашов, А.~В.~Кельманов
\paper $2$-приближенный алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов
\jour Автомат. и телемех.
\yr 2014
\issue 4
\pages 5--19
\mathnet{http://mi.mathnet.ru/at7528}
\transl
\jour Autom. Remote Control
\yr 2014
\vol 75
\issue 4
\pages 595--606
\crossref{https://doi.org/10.1134/S0005117914040018}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000334423100001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84899560990}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/at7528
  • http://mi.mathnet.ru/rus/at/y2014/i4/p5

    ОТПРАВИТЬ: 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. Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112  mathnet  mathscinet  elib; E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  crossref  isi
    2. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339  crossref  isi  elib
    3. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 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
    4. O. A. Zverkov, A. V. Seliverstov, V. A. Lyubetsky, “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
    5. L. I. Rubanov, A. V. Seliverstov, O. A. Zverkov, V. A. Lyubetsky, “A method for identification of highly conserved elements and evolutionary analysis of superphylum alveolata”, BMC Bioinformatics, 17 (2016), 385  crossref  isi  elib  scopus
    6. А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 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
  • Автоматика и телемеханика
    Просмотров:
    Эта страница:226
    Полный текст:29
    Литература:62
    Первая стр.:36
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020