Improved Deterministic Algorithms for Linear Programming in Low Dimensions

摘要

Chazelle and Matousek [J. Algorithms, 1996] presented a derandomization of Clarkson's sampling-based algorithm [J. ACM, 1995] for solving linear programswith 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 Bronnimann, Chazelle, and Matousek [SIAM J. Comput., 1999]. We first point out a much simpler derandomization of Clarkson's algorithm that avoids e-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.