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

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

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


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




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

Автоматика и телемеханика, 2010, выпуск 10, страницы 156–166 (Mi at902)  
Эта публикация цитируется в 10 научных статьях (всего в 10 статьях)

Параллельные и распределенные системы

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

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

a Московский государственный университет им. М. В. Ломоносова
b Институт системного анализа РАН, Москва
c Вычислительный центр РАН, Москва
PDF полного текста (181 kB) Список цитирования (10)
Список литературы:
PDF
HTML
Аннотация: Исследуется параллельная сложность решения задач оптимизации методом ветвей и границ. Рассматривается стандартная схема реализации метода ветвей и границ на параллельной системе, при которой вначале работает только один из процессоров, после чего полученные подзадачи передаются для обработки другим процессорам. Для этой схемы найдена нижняя оценка параллельной сложности, независящая от задачи. Изучается сложность рассматриваемой схемы для задачи о булевом ранце. Для классического алгоритмически трудного примера получены оценки параллельной сложности и показано, что эти оценки совпадают по порядку между собой и с общей нижней оценкой параллельной сложности. Тем самым показано, что общая нижняя оценка достигается по порядку для некоторых оптимизационных задач.
Статья представлена к публикации членом редколлегии: А. А. Лазарев

Поступила в редакцию: 12.01.2010
Англоязычная версия:
Automation and Remote Control, 2010, Volume 71, Issue 10, Pages 2152–2161
DOI: https://doi.org/10.1134/S0005117910100140
Реферативные базы данных:
Тип публикации: Статья
Образец цитирования: Р. М. Колпаков, М. А. Посыпкин, И. Х. Сигал, “О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ”, Автомат. и телемех., 2010, № 10, 156–166; Autom. Remote Control, 71:10 (2010), 2152–2161
Цитирование в формате AMSBIB
\RBibitem{KolPosSig10}
\by Р.~М.~Колпаков, М.~А.~Посыпкин, И.~Х.~Сигал
\paper О~нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ
\jour Автомат. и телемех.
\yr 2010
\issue 10
\pages 156--166
\mathnet{http://mi.mathnet.ru/at902}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2779041}
\zmath{https://zbmath.org/?q=an:1243.90249}
\transl
\jour Autom. Remote Control
\yr 2010
\vol 71
\issue 10
\pages 2152--2161
\crossref{https://doi.org/10.1134/S0005117910100140}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000283359800014}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77958460514}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/at902
  • https://www.mathnet.ru/rus/at/y2010/i10/p156
    • Эта публикация цитируется в следующих 10 статьяx:
    1. Si Thu Thant Sin, E. M. Portnov, A. M. Bain, 2023 International Russian Automation Conference (RusAutoCon), 2023, 786  crossref
    2. Sin Si Thu Thant, “The Parallel Processing Approach to the Dynamic Programming Algorithm of Knapsack Problem”, Proceedings of the 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (Elconrus), IEEE Nw Russia Young Researchers in Electrical and Electronic Engineering Conference, IEEE, 2021, 2252–2256  crossref  isi
    3. Kolpakov R., Posypkin M., “The Scalability Analysis of a Parallel Tree Search Algorithm”, Optim. Lett., 14:8 (2020), 2211–2226  crossref  mathscinet  isi  scopus
    4. Ignatov A., Gorchakov A., “Tool For Simulating Branch and Bound Computations”, Open Comput. Sci., 10:1 (2020), 112–116  crossref  isi  scopus
    5. 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
    6. Kolpakov R., Posypkin M., “A Criterion of Optimality of Some Parallelization Scheme For Backtrack Search Problem in Binary Trees”, Optimization and Applications, Optima 2019, Communications in Computer and Information Science, 1145, eds. Jacimovic M., Khachay M., Malkova V., Posypkin M., Springer International Publishing Ag, 2020, 455–464  crossref  isi
    7. Mikhail Posypkin, Si Thu Thant Sin, 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 2020, 2010  crossref
    8. Roman Kolpakov, Mikhail Posypkin, Communications in Computer and Information Science, 974, Optimization and Applications, 2019, 186  crossref
    9. Mikhail Posypkin, Si Thu Thant Sin, 2016 IEEE NW Russia Young Researchers in Electrical and Electronic Engineering Conference (EIConRusNW), 2016, 313  crossref
    10. Колпаков Р.М., Посыпкин М.А., “Об оценках вычислительной сложности варианта параллельной реализации метода ветвей и границ для задачи о ранце”, Известия Российской академии наук. Теория и системы управления, 2011, № 5, 74–82  mathscinet  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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Автоматика и телемеханика
    Статистика просмотров:
    Страница аннотации:564
    PDF полного текста:130
    Список литературы:59
    Первая страница:14
     
      Обратная связь:
    math-net2025_03@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025