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.