A SUBEXPONENTIAL BOUND FOR LINEAR-PROGRAMMING

We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected min[O(d(2)2(d)n),e(2 ro ot dln(n/root d)+Ot root d+lnn))] time in the unit cost model (where w e count the number of arithmetic operations on the numbers in the inpu t); to be precise, the algorithm computes the lexicographically smalle st nonnegative point satisfying n given linear inequalities in d varia bles. The expectation lover the internal randomizations performed by t he algorithm, and holds for any input. In conjunction with Clarkson's linear programming algorithm, this gives an expected bound of O(d(2)ne(Ot root dlnd))). The algorithm is presented in an abstract framework , which facilitates its application to several other related problems like computing the smallest enclosing hall (smallest volume enclosing ellipsoid) of n points in d-space, computing the distance of two n-ver tex (or n-facet) polytopes in d-space, and others. The subexponential running time can also be established for some of these problems (this relies on some recent results due to Gartner).