zbMATH — the first resource for mathematics

Linear programming in linear time when the dimension is fixed. (English) Zbl 0637.90064
It is demonstrated that the linear programming problem in d variables and n constraints can be solved in O(n) time when d is fixed. This bound follows from a multidimensional search technique which is applicable for quadratic programming as well. There is also developed an algorithm that is polynomial in both n and d provided d is bounded by a certain slowly growing function of n.

90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI