On Linear-time Deterministic Algorithms for Optimization Problems in Fixed Dimension
Report ID: TR-393-92Author: Chazelle, Bernard / Matousek, Jiri
Date: 1992-10-00
Pages: 16
Download Formats: |Postscript|
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.