Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming

Abstract

Let K be a polytope in ℝn defined by m linear inequalities. We give a new Markov chain algorithm to draw a nearly uniform sample from K. The underlying Markov chain is the first to have a mixing time that is strongly polynomial when started from a “central” point. We use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately.