Random walks on polytopes and an affine interior point method for linear programming

DOI10.1145/1536414.1536491zbMath1304.90138OpenAlexW2145089782MaRDI QIDQ5172751

Hariharan Narayanan, Ravindran Kannan

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536491

zbMATH Keywords

optimizationrandomized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Linear programming (90C05) Interior-point methods (90C51) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (5)

An empirical evaluation of walk-and-round heuristics for mixed integer linear programs ⋮ Geodesic Walks in Polytopes ⋮ Approximating the Pareto set of multiobjective linear programs via robust optimization ⋮ An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs ⋮ Randomized interior point methods for sampling and optimization

This page was built for publication: Random walks on polytopes and an affine interior point method for linear programming