A randomized polynomial-time simplex algorithm for linear programming
From MaRDI portal
Publication:2931369
DOI10.1145/1132516.1132524zbMATH Open1301.68262OpenAlexW2139819161MaRDI QIDQ2931369FDOQ2931369
Authors: Jonathan Kelner, Daniel A. Spielman 
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132524
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 (20)
- 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
- Title not available (Why is that?)
- Bayesian knowledge base tuning
- Set-valued state estimation of nonlinear discrete-time systems with nonlinear invariants based on constrained zonotopes
- A simple randomised algorithm for convex optimisation
- 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
- Title not available (Why is that?)
- From Parity and Payoff Games to Linear Programming
- Projective re-normalization for improving the behavior of a homogeneous conic linear system
- Random walks on polytopes and an affine interior point method for linear programming
- Title not available (Why is that?)
- A space decomposition-based deterministic algorithm for solving linear optimization problems
- 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)
