A Subexponential Bound for Linear Programming

Emo Welzl (joint work with Jiri Matousek, Micha Sharir) Institut für Informatik Freie Universität Berlin email: emo@inf.fu-berlin.de Report B 92-17 August 92

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-92-17.ps.gz
We present a simple randomized algorithm which solves linear programs with $n$ constraints and $d$ variables in expected\\ \hspace*{3cm}$\min\{O(d^2 2^d n), \lpcompl{d}{n}\}$\\[1mm] time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfying $n$ given linear inequalities in $d$ variables. The expectation is over the internal randomizations performed by the algorithm, and holds for any input. The algorithm is presented in an abstract framework, which facilitates its application to several other related problems like computing the smallest enclosing ball (smallest volume enclosing ellipsoid) of $n$ points in $d$-space, computing the distance of two $n$-vertex (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 G\"artner).\\ \noindent {\sc KEYWORDS:} computational geometry, combinatorial optimization, linear programming, smallest enclosing ball, smallest enclosing ellipsoid, randomized incremental algorithms.