Anzeige
Erschienen in:
1992 | ReviewPaper | Buchkapitel
A combinatorial bound for linear programming and related problems
verfasst von : Micha Sharir, Emo Welzl
Erschienen in: STACS 92
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.