Improved Deterministic Algorithms for Linear Programming in Low Dimensions

At SODA'93, Chazelle and Matoušek presented a derandomization of Clarkson's sampling-based algorithm [FOCS'88] for solving linear programs with n constraints and d variables in d (7+ o (1)) d n deterministic time. The time bound can be improved to d (5+ o (1)) d n with subsequent work by Brönnimann, Chazelle, and Matoušek [FOCS'93]. We first point out a much simpler derandomization of Clarkson's algorithm that avoids ∊ -approximations and runs in d (3 + o (1)) d n time. We then describe a few additional ideas that eventually improve the deterministic time bound to d (1/2+ o (1)) d n.

Authors

• Timothy M. Chan

Keywords

No keywords are indexed for this paper.