TY - GEN
T1 - Improved deterministic algorithms for linear programming in low dimensions
AU - Chan, Timothy M.
N1 - Publisher Copyright:
© Copyright (2016) by SIAM: Society for Industrial and Applied Mathematics.
PY - 2016
Y1 - 2016
N2 - At SODA'93, Chazelle and Matousek presented a derandom-ization of Clarkson's sampling-based algorithm [FOCS'88] for solving linear programs with n constraints and d variables in d(7+o(1))dn deterministic time. The time bound can be improved to d(5+o)(1)dn with subsequent work by Bronnimann, Chazelle, and Matousek [FOCS'93l. We first point out a much simpler derandomization of Clarkson's algorithm that avoids ϵ-approximations and runs in d(3+o(1))dn time. We then describe a few additional ideas that eventually improve the deterministic time bound to d(1/2+o(1))dn.
AB - At SODA'93, Chazelle and Matousek presented a derandom-ization of Clarkson's sampling-based algorithm [FOCS'88] for solving linear programs with n constraints and d variables in d(7+o(1))dn deterministic time. The time bound can be improved to d(5+o)(1)dn with subsequent work by Bronnimann, Chazelle, and Matousek [FOCS'93l. We first point out a much simpler derandomization of Clarkson's algorithm that avoids ϵ-approximations and runs in d(3+o(1))dn time. We then describe a few additional ideas that eventually improve the deterministic time bound to d(1/2+o(1))dn.
UR - http://www.scopus.com/inward/record.url?scp=84963657663&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84963657663&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974331.ch84
DO - 10.1137/1.9781611974331.ch84
M3 - Conference contribution
AN - SCOPUS:84963657663
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1213
EP - 1219
BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
A2 - Krauthgamer, Robert
PB - Association for Computing Machinery
T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Y2 - 10 January 2016 through 12 January 2016
ER -