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

We consider the problem of finding an $\epsilon-$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 $\epsilon$ 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(\sqrt{n} \ln \epsilon )$ steps of an interior point method. We show that the expected value of the number of steps required to obtain an $\epsilon-$optimal solution for a probabilistic linear programming model is at most $O(\min\{n^{1.5} m\sqrt{n}\ln(n)\}) + \log_{2} (\ln \epsilon)$.

Citation

Technical Report, TR2007-4, May, 2007, Department of Mathematics and Statistics, UMBC, http://www.math.umbc.edu/~kogan/technical_papers/2007/Ji_Potra.pdf