A simple polynomial-time rescaling algorithm for solving linear programs

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 with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis.

Authors

• John Dunagan
• Santosh S. Vempala

Keywords

• linear programming
• perceptron
• polynomial time