On linear-time deterministic algorithms for optimization problems in fixed dimension

Bernard Chazelle, Jiri Matousek

Research output: Contribution to conferencePaper

34 Scopus citations

Abstract

We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic one. The constant of proportionality is dO(d), which is better than for previously known such algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of n halfspaces) in linear time.

Original languageEnglish (US)
Pages281-290
Number of pages10
StatePublished - Jan 1 1993
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'On linear-time deterministic algorithms for optimization problems in fixed dimension'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Matousek, J. (1993). On linear-time deterministic algorithms for optimization problems in fixed dimension. 281-290. Paper presented at Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, .