A randomized algorithm for fixed-dimensional linear programming (Q1823854): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 09:51, 1 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A randomized algorithm for fixed-dimensional linear programming |
scientific article |
Statements
A randomized algorithm for fixed-dimensional linear programming (English)
0 references
1989
0 references
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.
0 references
