On the probabilistic complexity of finding an approximate solution for linear programming

AbstractWe consider the problem of finding an ε-optimal solution of a standard linear program with real data, i.e., of finding a feasible point at which the objective function value differs by at most ε from the optimal value. In the worst-case scenario the best complexity result to date guarantees that such a point is obtained in at most O(n|lnε|) steps of an interior-point method. We show that the expected value of the number of steps required to obtain an ε-optimal solution for a probabilistic linear programming model is at most O(min{n1.5,mnln(n)})+log2(|lnε|)