Рандомизированный распределенный адаптивный алгоритм решения задачи о максимальном потоке
Ключевые слова:
оптимизация с ограничениями, градиентный спуск, распределенные алгоритмы, рандомизированные алгоритмы, стохастическая аппроксимация, задача о максимальном потокеАннотация
В этой статье предлагается метод решения одной из классических задач оптимизации — задачи о максимальном потоке. Алгоритм основан на общей процедуре балансирования дуг и не дает выигрыша по времени работы относительно существующих методов, однако обладает другими полезными свойствами: простую реализацию на распределенных вычислительных системах, сохранение близости к оптимальному решению при изменении параметров сети во времени. Рассматривается два варианта алгоритма: рандомизированный и синхронный. Рандомизированная
версия использует идеи покоординатного градиентного спуска и рандомизированных алгоритмов стохастической аппроксимации. Рандомизированная версия оказывается предпочтительней, так как имеет такой же порядок сходимости (экспоненциальный), но при этом устойчива к помехам и допускает более простую распределенную реализацию по сравнению с синхронной версией.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2016 Николай Владимирович Мальковский
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
