On Linear-time Deterministic Algorithms for Optimization Problems in Fixed Dimension
Jiri Matousek (joint work with Bernard Chazelle)
Department of Computer Science
Charles University, CSFR
Report B 92-18
September 92
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-92-18.ps.gz
We show that with recently developed derandomization techniques,
one can convert Clarkson's
randomized algorithm for linear
programming in fixed dimension into a linear-time deterministic one.
The constant of proportionality is $d^{O(d)}$, which is better
than for previously known such algorithms. We show that the
algorithm works in a fairly general abstract setting,
which allows us to solve various
other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of $n$ halfspaces)
in linear time.\\[1mm]
{\bf Keywords:} Computational complexity, computational geometry, geometric optimization problem, randomized algorithm, derandomization