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

DOI10.1287/moor.1110.0519zbMath1243.65033OpenAlexW2123493177MaRDI QIDQ2884302

Hariharan Narayanan, Ravindran Kannan

Publication date: 24 May 2012

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1110.0519

zbMATH Keywords

algorithmpolytopesrandom walksinterior point methodslinear programsMarkov chain algorithm

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical mathematical programming methods (65K05) Linear programming (90C05) Interior-point methods (90C51) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical analysis or methods applied to Markov chains (65C40)

Related Items

On the mixing time of coordinate Hit-and-Run, Sampling from a log-concave distribution with projected Langevin Monte Carlo, Unnamed Item, John’s walk, The mixing time of the Dikin walk in a polytope -- a simple proof, Unnamed Item, Generalized affine scaling algorithms for linear programming problems, Unnamed Item