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

Bernard Chazelle, Jiri Matousek

Research output: Contribution to conferencePaperpeer-review

36 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 - 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

  • General Engineering

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