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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 2, 2006, том 13, номер 1, страницы 10–26 (Mi da15)  

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

Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях

Э. Х. Гимади, Ю. В. Глазков

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

Аннотация: Рассматривается $m$-слойная трёхиндексная планарная задача о назначениях, являющаяся модификацией классической трёхиндексной планарной задачи о назначениях. Эта задача NP-трудна при $m\geqslant2$. Предложен приближённый алгоритм решения задачи при $1<m<n/2$. Установлены оценки качества его работы в случае, когда входные данные (элементы матрицы размера $m\times n\times n$) являются независимыми одинаково распределёнными случайными величинами со значениями на отрезке $[a_n,b_n]$, где $b_n>a_n>0$. Алгоритм имеет временную сложность $O(mn^2+m^{7/2})$. Показано, что в случае равномерного распределения (а также распределения минорируемого типа) алгоритм является асимптотически точным, если $m=\Theta(n^{1-\theta})$ и $b_n/a_n=o(n^\theta)$ для любой константы $\theta$, $0<\theta<1$.
Библ. 23.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2007, 1:4, 442–452

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


Образец цитирования: Э. Х. Гимади, Ю. В. Глазков, “Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях”, Дискретн. анализ и исслед. опер., сер. 2, 13:1 (2006), 10–26; J. Appl. Industr. Math., 1:4 (2007), 442–452

Цитирование в формате AMSBIB
\RBibitem{GimGla06}
\by Э.~Х.~Гимади, Ю.~В.~Глазков
\paper Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях
\jour Дискретн. анализ и исслед. опер., сер.~2
\yr 2006
\vol 13
\issue 1
\pages 10--26
\mathnet{http://mi.mathnet.ru/da15}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2288949}
\zmath{https://zbmath.org/?q=an:1249.90221}
\transl
\jour J. Appl. Industr. Math.
\yr 2007
\vol 1
\issue 4
\pages 442--452
\crossref{https://doi.org/10.1134/S1990478907040072}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-37249071814}


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

    ОТПРАВИТЬ: 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. Yokoya D., Duin C.W., Yamada T., “A reduction approach to the repeated assignment problem”, European J. Oper. Res., 210:2 (2011), 185–193  crossref  mathscinet  zmath  isi  elib  scopus
    2. Л. Г. Афраймович, “Многоиндексные транспортные задачи с декомпозиционной структурой”, Автомат. и телемех., 2012, № 1, 130–147  mathnet; L. G. Afraimovich, “Multi-index transport problems with decomposition structure”, Autom. Remote Control, 73:1 (2012), 118–133  crossref  isi
    3. Афраймович Л.Г., Катеров А.С., “Трех- и четырехиндексные задачи с вложенной структурой”, Вестник нижегородского университета им. Н.И. Лобачевского, 2012, 163–169  elib
    4. Л. Г. Афраймович, “Многоиндексные транспортные задачи с $2$-вложенной структурой”, Автомат. и телемех., 2013, № 1, 116–134  mathnet; L. G. Afraimovich, “Multiindex transportation problems with $2$-embedded structure”, Autom. Remote Control, 74:1 (2013), 90–104  crossref  isi
    5. Э. Х. Гимади, Ю. В. Глазков, О. Ю. Цидулко, “Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках”, Дискретн. анализ и исслед. опер., 21:1 (2014), 15–29  mathnet  mathscinet; E. Kh. Gimadi, Yu. V. Glazkov, O. Yu. Tsidulko, “The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations”, J. Appl. Industr. Math., 8:2 (2014), 208–217  crossref  isi
    6. Л. Г. Афраймович, “Эвристический метод решения целочисленных декомпозиционных многоиндексных задач”, Автомат. и телемех., 2014, № 8, 3–18  mathnet; L. G. Afraimovich, “A heuristic method for solving integer-valued decompositional multiindex problems”, Autom. Remote Control, 75:8 (2014), 1357–1368  crossref  isi
    7. Э. Х. Гимади, Е. Ю. Шин, “Вероятностный анализ алгоритма нахождения в графе минимального остовного дерева с ограниченным снизу диаметром”, Дискретн. анализ и исслед. опер., 22:4 (2015), 5–20  mathnet  crossref  mathscinet  elib; E. Kh. Gimadi, E. Yu. Shin, “Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below”, J. Appl. Industr. Math., 9:4 (2015), 480–488  crossref
    8. Gimadi E.Kh., “Efficient Algorithms With Performance Guarantees For Some Problems of Finding Several Discrete Disjoint Subgraphs in Complete Weighted Graph”, Appl. Math. Comput., 255 (2015), 84–91  crossref  mathscinet  zmath  isi  elib  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:458
    Полный текст:121
    Литература:37
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019