Алгоритм аукциона: различия между версиями
Перейти к навигации
Перейти к поиску
| [досмотренная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) Нет описания правки |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 34: | Строка 34: | ||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
[[en:Auction algorithm]] | |||
Версия от 14:09, 14 марта 2018
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм аукциона[1] предназначен для решения задачи о назначениях. Алгоритм имитирует проведение аукциона, в ходе которого агенты повышают цену за назначение той или иной задачи. Алгоритм аукциона может быть реализован и в распределённой среде[2], когда информации о текущих котировках поступают агентам с некоторым запаздыванием.
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.
- ↑ Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.