A simple polynomial-time rescaling algorithm for solving linear programs Export

@article{citeulike:2575535, abstract = {Abstract\ \ The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis.}, author = {Dunagan, John and Vempala, Santosh}, citeulike-article-id = {2575535}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s10107-007-0095-7}, day = {19}, doi = {10.1007/s10107-007-0095-7}, journal = {Mathematical Programming}, keywords = {algorithm, optimization}, month = {July}, number = {1}, pages = {101--114}, posted-at = {2008-03-24 00:03:43}, priority = {3}, title = {A simple polynomial-time rescaling algorithm for solving linear programs}, url = {http://dx.doi.org/10.1007/s10107-007-0095-7}, volume = {114}, year = {2008} }

TY - JOUR ID - citeulike:2575535 L3 - citeulike-article-id:2575535 N2 - Abstract  The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis. IS - 1 JF - Mathematical Programming EP - 114 TI - A simple polynomial-time rescaling algorithm for solving linear programs VL - 114 SP - 101 KW - algorithm KW - optimization AU - Dunagan, John AU - Vempala, Santosh PY - 2008/07/19/ UR - http://dx.doi.org/10.1007/s10107-007-0095-7 ER -