- On the probabilistic complexity of finding an approximate solution for linear programming Jun Ji(jjikennesaw.edu) Florian A. Potra(potramath.umbc.edu) Abstract: 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)$. Keywords: Linear Programming; Interior-Point Algorithm; Average Complexity; Approximate Solution Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) 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 Download: [PDF]Entry Submitted: 05/18/2007Entry Accepted: 05/19/2007Entry Last Modified: 05/18/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.