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

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

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


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




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

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

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

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

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

a Московский государственный университет им. М. В. Ломоносова
b Институт системного анализа РАН, Москва
c Вычислительный центр РАН, Москва
PDF полного текста (181 kB) Список цитирования (11) Английская версия
Список литературы:
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{https://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
    • Эта публикация цитируется в следующих 11 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Автоматика и телемеханика
    Статистика просмотров:
    Страница аннотации:675
    PDF полного текста:161
    Список литературы:87
    Первая страница:14
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025