No. 25 (242), issue 9Pages 107 - 118

THE PARALLEL SIMPLEX-METHOD ACHIEVEMENTS FOR ERRORLESS SOLVING OF LINEAR PROGRAMMING PROBLEMS

A.V. Panyukov, V.V. Gorbik
Techniques of obtaining exact solutions of linear programming problems are subjects of this paper. Absolute accuracy are arrived at implementation of simplex-algorithm with exact rational-fractional computation. In this case if $m$ is minimal of problem dimensions, and $l$ is number of bits for a source data item then space complexity are no more $4lm^4+o(m^3)$, one iteration time complexity are no more $O(lm^4)$, and paralleling efficiency (i.e. ratio of acceleration to number of processors) asymptotical estimate are 100
Full text
Keywords
linear programming, simplex method, distributed computing, parallel computing, rational computations, optimization, arbitrary precision, interval arithmetic.