Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах - Сергиенко, А.М.; Симоненко, В.П.; Симоненко, А.В. (Системні дослідження та інформаційні технології, 2016)
Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n³) до O(n¹,⁵ log n). . Подход применяется в алгоритме адаптивного мультианализа, который основан на предварительном анализе и коррекции графа паросочетаний. При его применении к матрицам графов с коэффициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной.