On Linear-time Deterministic Algorithms for Optimization Problems in Fixed Dimension
Report ID:
TR-413-93
Authors:
Date:
February 1993
Pages:
16
Download Formats:
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, 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 Algorithms
21(3), 1996, pp. 579-595.