On Linear-time Deterministic Algorithms for Optimization Problems in Fixed Dimension

Abstract:

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.

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 Algorithms 21(3),
1996, pp. 579-595.