ON LINEAR-TIME DETERMINISTIC ALGORITHMS FOR OPTIMIZATION PROBLEMS IN FIXED DIMENSION

We show that with recently developed derandomization techniques, one c an convert Clarkson's randomized algorithm for linear programming in f ixed dimension into a linear-time deterministic algorithm. The constan t of proportionality is d(O(d)), which is better than those for previo usly known algorithms. We show that the algorithm works in a fairly ge neral abstract setting, which allows us to solve various other problem s, e.g., computing the minimum-volume ellipsoid enclosing a set of n p oints and finding the maximum volume ellipsoid in the intersection of n halfspaces. (C) 1996 Academic Press, Inc.