  


On the probabilistic complexity of finding an approximate solution for linear programming
Jun Ji(jjikennesaw.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 worstcase 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; InteriorPoint Algorithm; Average Complexity; Approximate Solution Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Technical Report, TR20074, 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 Modify/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  