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.
