Рандомизированный распределенный адаптивный алгоритм решения задачи о максимальном потоке

Николай Владимирович Мальковский

Research output

Abstract

В этой статье предлагается метод решения одной из классических задач оптимизации -- задачи о максимальном потоке. Алгоритм основан на общей процедуре балансирования дуг и не дает выигрыша по времени работы относительно существующих методов, однако обладает другими полезными свойствами: простую реализацию на распределенных вычислительных системах, сохранение близости к оптимальному решению при изменении параметров сети во времени. Рассматривается два варианта алгоритма: рандомизированный и синхронный. Рандомизированная версия использует идеи покоординатного градиентного спуска и рандомизированных алгоритмов стохастической аппроксимации. Рандомизированная версия оказывается предпочтительней, так как имеет такой же порядок сходимости (экспоненциальный), но при этом устойчива к помехам и допускает более простую распределенную реализацию по сравнению с синхронной версией.
Original languageUndefined
JournalКОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ
Publication statusPublished - 2016
Externally publishedYes

Cite this