On the probabilistic complexity of finding an approximate solution for linear programming (Q2483208)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the probabilistic complexity of finding an approximate solution for linear programming |
scientific article |
Statements
On the probabilistic complexity of finding an approximate solution for linear programming (English)
0 references
28 April 2008
0 references
The authors study the problem of finding an \(\varepsilon\)-optimal solution to a real-life linear program. They begin with a useful overview of the literature on existing probabilistic and worst-case estimations of the complexity of solving linear programs and then continue by presenting their probabilistic model for which they then describe (with proof) asymptotic results, convergence properties and average number of iterations required to obtain a solution with a value within \(\varepsilon\) of the optimal. Several useful theorems are proven in the course of this paper, which concludes with a list of very useful references.
0 references
linear programming
0 references
interior point algorithm
0 references
average complexity
0 references
approximate solution
0 references
worst-case estimations
0 references
probabilistic model
0 references
0 references
0 references
0 references
0 references
0 references
0 references