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/2007
Entry Accepted: 05/19/2007
Entry Last Modified: 05/18/2007

Modify/Update this entry