## 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.