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

Аннотация

В работе рассмотрены подходы к решению задачи линейного программирования с абсолютной точностью, достигаемой применением в алгоритмах симплекс-метода дробно-рациональных вычислений без округления. Если при этом $m$ - минимальная из размерностей задачи, $l$ - число бит, необходимых под один численный элемент исходных данных, то пространственная сложность алгоритма не превосходит $4lm^4+o(m^3)$, при этом вычислительная сложность одной итерации симплекс-метода не превосходит $O(lm^4)$, а эффективность распараллеливания (т.е. отношение ускорения к числу процессоров) в предложенной реализации параллельного алгоритма составляет в асимптотике 100