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 -