1992 | ReviewPaper | Chapter
A combinatorial bound for linear programming and related problems
Authors : Micha Sharir, Emo Welzl
Published in: STACS 92
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected O(d32dn) time. The expectation is over the internal randomizations performed by the algorithm, and holds for any input.The algorithm is presented in an abstract framework, which facilitates its application to a large class of problems, including computing smallest enclosing balls (or ellipsoids) of finite point sets in d-space, computing largest balls (ellipsoids) in convex polytopes, convex programming in general, etc.