×

The parallel simplex-method achievements for errorless solving of linear programming problems. (Russian. English summary) Zbl 1352.90062

Summary: Techniques for obtaining exact solutions of linear programming problems are the subjects of this paper. Absolute accuracy is derived at the implementation of simplex-algorithms with exact rational-fractional computation. In this case, if \(m\) is minimal of problem dimensions, and \(l\) is the number of bits for a source data item, then the space complexity is not greater than \(4lm^4+o(m^3)\), one iteration time complexity is not greater than \(O(lm^4)\), and the paralleling efficiency (i.e., the ratio of acceleration to the number of processors) asymptotical estimate is 100%.

MSC:

90C05 Linear programming
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: MNR