Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Пред- ставлены теоремы, позволяющие для двудольных графов, отображающих пре- тендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с ( ) 3 O n до ( log ) 1,5 O n n . Подход применяется в алгоритме адап- тивного мультианализа, который основан на предварительном анализе и кор- рекции графа паросочетаний. При его применении к матрицам графов с коэф- фициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной.
