Improved Deterministic Algorithms for Linear Programming in Low Dimensions
Timothy M. Chan · ACM Transactions on Algorithms · 2018
Chazelle and Matoušek [ J. Algorithms , 1996] presented a derandomization of Clarkson’s sampling-based algorithm [ J. ACM , 1995] 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 [ SIAM J. Comput. , 1999]. 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 .