ICS Theory Group

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.