A Subexponential Bound for Linear Programming

@inproceedings{citeulike:749656, abstract = {We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected minfO(d 2 2 d n); e 2 p d ln(n= p d )+O( p d+ln n) g time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfying n given linear inequalities in d variables. The expectation is over the internal randomizations performed...}, author = {Matousek, Jiri and Sharir, Micha and Welzl, Emo }, booktitle = {Symposium on Computational Geometry}, citeulike-article-id = {749656}, keywords = {bregmanclustering}, pages = {1--8}, posted-at = {2006-07-10 21:24:43}, priority = {2}, title = {A Subexponential Bound for Linear Programming}, url = {http://citeseer.ist.psu.edu/matousek96subexponential.html}, year = {1992} }

TY - CONF ID - citeulike:749656 L3 - citeulike-article-id:749656 TI - A Subexponential Bound for Linear Programming T2 - Symposium on Computational Geometry SP - 1 EP - 8 N2 - We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected minfO(d 2 2 d n); e 2 p d ln(n= p d )+O( p d+ln n) g time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfying n given linear inequalities in d variables. The expectation is over the internal randomizations performed... KW - bregmanclustering AU - Matousek, Jiri AU - Sharir, Micha AU - Welzl, Emo PY - 1992/// UR - http://citeseer.ist.psu.edu/matousek96subexponential.html ER -