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

DOI10.1137/1.9781611973402.65MaRDI QIDQ5384026zbMATH OpenOpenAlexFDO

Authors Thomas Dueholm Hansen, Uri Zwick, Mike 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) Randomized algorithms (68W20) Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Recommendations

• Random edge can be exponential on abstract cubes
• Two New Bounds for the Random‐Edge Simplex‐Algorithm
• scientific article; zbMATH DE number 125468
• New bounds for edge-cover by random walk
• Further results on random cubic planar graphs
• An improved upper bound on the crossing number of the hypercube
• scientific article; zbMATH DE number 4212109
• Randomized simplex algorithms on Klee-Minty cubes
• Improved upper bounds on the growth constants of polyominoes and polycubes
• Improved upper bounds on the growth constants of polyominoes and polycubes

Cited in

(13)

• Improved bound on the worst case complexity of policy iteration
• Unique end of potential line
• The complexity of optimization on grids
• A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
• Geometric random edge
• Random edge can be exponential on abstract cubes
• Jumping Doesn’t Help in Abstract Cubes
• The complexity of all-switches strategy improvement
• Random-Edge Is Slower Than Random-Facet on Abstract Cubes
• The niceness of unique sink orientations
• Unique End of Potential Line
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• An efficient algorithm for vertex enumeration of arrangement

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384026)