June 5, Spring Quarter 2009: Thoery Seminar
1:00pm in 253 ICS
Linear Programming in Linear Time When the Dimension Is Fixed
by Nimrod Megiddo,
J. ACM vol. 31, issue 1, pp. 114-127, 1984.
Presented by Kevin Wortman
Abstract. 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.