A randomized algorithm for fixed-dimensional linear programming

Autor: Dyer, M. E., Frieze, A. M.
Zdroj: Mathematical Programming; May 1989, Vol. 44 Issue: 1-3 p203-212, 10p
Abstrakt: We give a (Las Vegas) randomized algorithm for linear programming in a fixed dimensiond for which the expected computation time is $$O(d^{(3 + \varepsilon _d )d} n)$$ , where limd?8ed = 0. This improves the corresponding worst-case complexity, $$O(3^{d^2 } n)$$ . The method is based on a recent idea of Clarkson. Two variations on the algorithm are examined briefly.
Databáze: Supplemental Index
Externí odkaz: