Random-Edge Is Slower Than Random-Facet on Abstract Cubes

DOI10.4230/LIPICS.ICALP.2016.51MaRDI QIDQ4598190zbMATH OpenOpenAlexFDO

Authors Thomas Dueholm Hansen, Uri Zwick

Publication date 19 December 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2016.51

zbMATH Keywords

acyclic unique sink orientationslinear programmingpivoting rulessimplex algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Recommendations

• Random edge can be exponential on abstract cubes
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• The Random‐Facet simplex algorithm on combinatorial cubes
• Randomized simplex algorithms on Klee-Minty cubes
• Two New Bounds for the Random‐Edge Simplex‐Algorithm
• Random polytopes in the d-dimensional cube
• Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
• scientific article; zbMATH DE number 5149093
• Approximation by random polytopes has low complexity
• Asymptotically efficient triangulations of the d-cube

Cited in

(8)

• Randomized simplex algorithms on Klee-Minty cubes
• Random edge can be exponential on abstract cubes
• The Random‐Facet simplex algorithm on combinatorial cubes
• The niceness of unique sink orientations
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• The Klee–Minty random edge chain moves with linear speed
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• Two New Bounds for the Random‐Edge Simplex‐Algorithm

This page was built for publication: Random-Edge Is Slower Than Random-Facet on Abstract Cubes

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