A randomized algorithm for fixed-dimensional linear programming (Q1823854): Difference between revisions

Using the idea of \textit{K. L. Clarkson} [Discrete Comput. Geom. 2, 195-222 (1987; Zbl 0615.68037)] the authors give a (Las Vegas) randomized algorithm for linear programming in a fixed dimension d. For this algorithm the expected computation time is \(O(d^{(3+\epsilon_ d)d}n)\), where \(\lim_{d\to \infty}\epsilon_ d=O\). Two variations on the algorithm are examined.