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

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

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



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






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


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

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

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

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

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

a Московский государственный университет им. М. В. Ломоносова
b Институт системного анализа РАН, Москва
c Вычислительный центр РАН, Москва

Аннотация: Исследуется параллельная сложность решения задач оптимизации методом ветвей и границ. Рассматривается стандартная схема реализации метода ветвей и границ на параллельной системе, при которой вначале работает только один из процессоров, после чего полученные подзадачи передаются для обработки другим процессорам. Для этой схемы найдена нижняя оценка параллельной сложности, независящая от задачи. Изучается сложность рассматриваемой схемы для задачи о булевом ранце. Для классического алгоритмически трудного примера получены оценки параллельной сложности и показано, что эти оценки совпадают по порядку между собой и с общей нижней оценкой параллельной сложности. Тем самым показано, что общая нижняя оценка достигается по порядку для некоторых оптимизационных задач.

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

Англоязычная версия:
Automation and Remote Control, 2010, 71:10, 2152–2161

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

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

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

Образец цитирования: Р. М. Колпаков, М. А. Посыпкин, И. Х. Сигал, “О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ”, Автомат. и телемех., 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://www.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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000283359800014}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77958460514}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/at902
  • http://mi.mathnet.ru/rus/at/y2010/i10/p156

    ОТПРАВИТЬ: 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. Колпаков Р.М., Посыпкин М.А., “Об оценках вычислительной сложности варианта параллельной реализации метода ветвей и границ для задачи о ранце”, Известия Российской академии наук. Теория и системы управления, 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
  • Автоматика и телемеханика
    Просмотров:
    Эта страница:295
    Полный текст:81
    Литература:27
    Первая стр.:14
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019