Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-413-93

Authors:

Date:

February 1993

Pages:

16

Download Formats:

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, e.g., computing the minimum-volume ellipsoid enclosing a set

of $n$ points, finding the maximum volume ellipsoid in the

intersection of $n$ halfspaces.

- This technical report has been published as
- On Linear-time Deterministic Algorithms for Optimization Problems

in Fixed Dimension.

Bernard Chazelle and Jiri Matousek,Journal of Algorithms21(3), 1996, pp. 579-595.