Improved upper bounds for Random-Edge and Random-Jump on abstract cubes

DOI10.1137/1.9781611973402.65zbMath1421.68084OpenAlexW4239254359MaRDI QIDQ5384026

Thomas Dueholm Hansen, Uri Zwick, Mike S. Paterson

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/16079d3f5838b17ed5b32b2d99229b02a9f6d891

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Randomized algorithms (68W20) Extreme-point and pivoting methods (90C49)

Related Items (8)

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations ⋮ Geometric random edge ⋮ Unique end of potential line ⋮ Unnamed Item ⋮ Improved bound on the worst case complexity of policy iteration ⋮ Unnamed Item ⋮ Unique End of Potential Line ⋮ The complexity of optimization on grids

This page was built for publication: Improved upper bounds for Random-Edge and Random-Jump on abstract cubes