TY - JOUR
T1 - On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
AU - Chazelle, Bernard
AU - Matoušek, Jiří
N1 - Funding Information:
* Supported in part by NSF Grant CCR-90-02352 and the Geometry Center. ²Supported in part by Humboldt Research Fellowship.
PY - 1996/11
Y1 - 1996/11
N2 - 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 algorithm. The constant of proportionality is dO(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set of n points and finding the maximum volume ellipsoid in the intersection of n halfspaces.
AB - 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 algorithm. The constant of proportionality is dO(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set of n points and finding the maximum volume ellipsoid in the intersection of n halfspaces.
UR - http://www.scopus.com/inward/record.url?scp=13544265613&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=13544265613&partnerID=8YFLogxK
U2 - 10.1006/jagm.1996.0060
DO - 10.1006/jagm.1996.0060
M3 - Article
AN - SCOPUS:13544265613
VL - 21
SP - 579
EP - 597
JO - Journal of Algorithms
JF - Journal of Algorithms
SN - 0196-6774
IS - 3
ER -