A randomized polynomial-time simplex algorithm for linear programming
From MaRDI portal
Recommendations
- A randomized algorithm for fixed-dimensional linear programming
- Randomized combinatorial algorithms for linear programming when the dimension is moderately high
- On optimality of a polynomial algorithm for random linear multidimensional assignment problem
- scientific article; zbMATH DE number 1003270
- Randomized rounding for the largest simplex problem
- A new polynomial-time algorithm for linear programming
- scientific article; zbMATH DE number 4121753
- Linear programming — Randomization and abstract frameworks
- A fast simplex algorithm for linear programming
- Towards a Genuinely Polynomial Algorithm for Linear Programming
Cited in
(28)- A simple polynomial-time rescaling algorithm for solving linear programs
- A double-pivot simplex algorithm and its upper bounds of the iteration numbers
- Moser's shadow problem
- A friendly smoothed analysis of the simplex method
- Linear programming — Randomization and abstract frameworks
- scientific article; zbMATH DE number 1003270 (Why is no real title available?)
- Solving totally unimodular LPs with the shadow vertex algorithm
- Bayesian knowledge base tuning
- A simple randomised algorithm for convex optimisation
- Set-valued state estimation of nonlinear discrete-time systems with nonlinear invariants based on constrained zonotopes
- Guaranteed methods based on constrained zonotopes for set-valued state estimation of nonlinear discrete-time systems
- An exponential lower bound for Zadeh's pivot rule
- From Parity and Payoff Games to Linear Programming
- scientific article; zbMATH DE number 4216294 (Why is no real title available?)
- Upper and lower bounds on the smoothed complexity of the simplex method
- Random walks on polytopes and an affine interior point method for linear programming
- Exponential lower bounds for many pivot rules for the simplex method
- Projective re-normalization for improving the behavior of a homogeneous conic linear system
- Geometric random edge
- Random walks on polytopes and an affine interior point method for linear programming
- scientific article; zbMATH DE number 2196286 (Why is no real title available?)
- A unified worst case for classical simplex and policy iteration pivot rules
- Interior point methods are not worse than simplex
- A space decomposition-based deterministic algorithm for solving linear optimization problems
- Randomized MWU for positive LPs
- A characterization theorem and an algorithm for a convex hull problem
- George Dantzig's impact on the theory of computation
- The worst-case running time of the random simplex algorithm is exponential in the height
This page was built for publication: A randomized polynomial-time simplex algorithm for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931369)
