Tangentially / A Machine Learning Blog Aaron Defazio, Machine Learning Researcher & Data Scientist

I recently came across this remarkable randomized algorithm due to Seidel (1991) for linear programming in 2 dimensions that takes only time O(n) for n constraints (in expectation). It's definitely worth a close inspection, so I thought I would write a short article about it. Note that my presentation of this algorithm assumes that there are no redundant or colinear constraints, that the solution is bounded, and that the solution for each subproblem encountered is unique. These assumptions are easy to remove without slowing the algorithm down, but they complicate the presentation a little. OUTPUT: A point v in the polytope defined by H minimizing cTv.