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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references