Loading [MathJax]/jax/output/SVG/config.js
Журнал вычислительной математики и математической физики
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

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

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


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




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

Журнал вычислительной математики и математической физики, 2006, том 46, номер 12, страницы 2289–2304 (Mi zvmmf374)  
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)

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

М. А. Посыпкинa, И. Х. Сигалb

a 109004 Москва, пр-т 60-летия Октября, 9, ИСА РАН
b 119991 Москва, ул. Вавилова, 40, ВЦ РАН
PDF полного текста (2432 kB) Список цитирования (8)
Аннотация: Исследована эффективность распараллеливания в задачах дискретной оптимизации. Проведен теоретический анализ и сравнение двух параллельных реализаций метода ветвей и границ. Построена математическая модель процесса вычислений, с помощью которой получены оценки для максимально возможного значения ускорения. Приводятся примеры задач, для которых применение любого из рассматриваемых алгоритмов не позволяет ускорить процесс решения задачи. Библ. 20. Фиг. 8. Табл. 1.
Ключевые слова: алгоритмы параллельных вычислений, дискретная оптимизация, метод ветвей и границ, оценка ускорения, модель процесса вычислений.
Поступила в редакцию: 09.02.2006
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2006, Volume 46, Issue 12, Pages 2187–2202
DOI: https://doi.org/10.1134/S0965542506120165
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.854
Образец цитирования: М. А. Посыпкин, И. Х. Сигал, “Оценки ускорения для некоторых вариантов параллельной реализации метода ветвей и границ”, Ж. вычисл. матем. и матем. физ., 46:12 (2006), 2289–2304; Comput. Math. Math. Phys., 46:12 (2006), 2187–2202
Цитирование в формате AMSBIB
\RBibitem{PosSig06}
\by М.~А.~Посыпкин, И.~Х.~Сигал
\paper Оценки ускорения для некоторых вариантов параллельной реализации метода ветвей и границ
\jour Ж. вычисл. матем. и матем. физ.
\yr 2006
\vol 46
\issue 12
\pages 2289--2304
\mathnet{http://mi.mathnet.ru/zvmmf374}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2344973}
\transl
\jour Comput. Math. Math. Phys.
\yr 2006
\vol 46
\issue 12
\pages 2187--2202
\crossref{https://doi.org/10.1134/S0965542506120165}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33846183271}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf374
  • https://www.mathnet.ru/rus/zvmmf/v46/i12/p2289
    • Эта публикация цитируется в следующих 8 статьяx:
    1. Kolpakov R., Posypkin M., “Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem”, Open Comput. Sci., 11:1 (2020), 116–126  crossref  isi
    2. M. G. Dobrosotskikh, “CONSIDERATION OF STOCHASTIC IMPACTS IN THE CONSTRUCTION SCHEDULING”, Proceedings of the SWSU, 22:6 (2019), 61  crossref
    3. Alexandre Dolgui, Evgeny Gafarov, “Can a Branch and Bound algorithm solve all instances of SALBP-1 efficiently?”, IFAC-PapersOnLine, 52:13 (2019), 2788  crossref
    4. Yury Evtushenko, Yana Golubeva, Yury Orlov, Mikhail Posypkin, Communications in Computer and Information Science, 687, Supercomputing, 2016, 356  crossref
    5. Колпаков Р.М., Посыпкин М.А., “Об оценках вычислительной сложности варианта параллельной реализации метода ветвей и границ для задачи о ранце”, Известия Российской академии наук. Теория и системы управления, 2011, № 5, 74–82  mathscinet  zmath  elib; Kolpakov R.M., Posypkin M.A., “Estimating the computational complexity of one variant of parallel realization of the branch-and-bound method for the knapsack problem”, Journal of Computer and Systems Sciences International, 50:5 (2011), 756–765  crossref  mathscinet  zmath  isi  scopus
    6. Р. М. Колпаков, М. А. Посыпкин, И. Х. Сигал, “О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ”, Автомат. и телемех., 2010, № 10, 156–166  mathnet  mathscinet  zmath; R. M. Kolpakov, M. A. Posypkin, I. Kh. Sigal, “On a lower bound on the computational complexity of a parallel implementation of the branch-and-bound method”, Autom. Remote Control, 71:10 (2010), 2152–2161  crossref  isi
    7. Дудин Е.Б., Сметанин Ю.Г., “Проблемы и перспективы моделирования информационно-вычислительных сетей (обзор)”, Научно-техническая информация. Сер. 2: Информационные процессы и системы, 2010, № 12, 1–9  elib
    8. E. B. Dudin, Yu. G. Smetanin, “Problems and prospects of modeling computer information networks. A review”, Autom. Doc. Math. Linguist., 44:6 (2010), 287  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Статистика просмотров:
    Страница аннотации:493
    PDF полного текста:339
    Первая страница:1
     
      Обратная связь:
    math-net2025_03@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025