On the average number of steps of the simplex method of linear programming
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 5968600 (Why is no real title available?)
- scientific article; zbMATH DE number 3126031 (Why is no real title available?)
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 3483788 (Why is no real title available?)
- scientific article; zbMATH DE number 3332062 (Why is no real title available?)
- scientific article; zbMATH DE number 3069630 (Why is no real title available?)
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- A convergent process of price adjustment and global Newton methods
- A new linear programming algorithm - better or worse than the simplex method?
- Complexity of linear programming
- Computational complexity of complementary pivot methods
- On Algorithms for Solvingf(x)=0
- On the role of the Heisenberg group in harmonic analysis
- Random polytopes: Their definition, generation and aggregate properties
- The Average number of pivot steps required by the Simplex-Method is polynomial
- The Gauss-Bonnet Theorem for Riemannian Polyhedra
- The Solution of Systems of Piecewise Linear Equations
- The fundamental theorem of algebra and complexity theory
Cited in
(52)- Fast finite methods for a system of linear inequalities
- Monotone meshfree methods for linear elliptic equations in non-divergence form via nonlocal relaxation
- Average polynomial time complexity of some NP-complete problems
- On the average speed of Lemke's algorithm for quadratic programming
- On the expected number of linear complementarity cones intersected by random and semi-random rays
- A new family of exponential LP problems
- Asymptotic optimality of a transport-problem plan constructed by the minimum-element method
- A friendly smoothed analysis of the simplex method
- Diophantine cryptography over infinite groups
- A new simple homotopy algorithm for linear programming. I
- Parametric linear programming and anti-cycling pivoting rules
- Some remarks on Karmarkar's potential function
- Invertibility of random fredholm operators
- Polyhedral Combinatorics in Combinatorial Optimization
- Average-case optimization analysis for distributed consensus algorithms on regular graphs
- Recent developments in information-based complexity
- Experiments with external pivoting
- Recognizing one-dimensional Euclidean preference profiles
- Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
- Optimal search algorithm for extrema of a discrete periodic bimodal function
- New results on the average behavior of simplex algorithms
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Quantitative simulations by matrices
- Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
- Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
- Exponential lower bounds for finding Brouwer fixed points
- Simplex-inspired algorithms for solving a class of convex programming problems
- Random linear programs with many variables and few constraints
- From Parity and Payoff Games to Linear Programming
- Upper and lower bounds on the smoothed complexity of the simplex method
- Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem
- On Estimating Optimal Bases for Linear Programs
- Estimating the volume of solution space for satisfiability modulo linear real arithmetic
- Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
- On the efficiency of algorithms of analysis
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
- Upper and lower bounds on the smoothed complexity of the simplex method
- Random inequality constraint systems with few variables
- Probabilistic analysis of a differential equation for linear programming
- The work of Steve Smale
- A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps
- Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
- Average case optimality
- Statistical complexity of the power method for Markov chains
- A quadratically convergent method for linear programming
- Halting time is predictable for large models: a universality property and average-case analysis
- Conditioning of random conic systems under a general family of input distributions
- George Dantzig's impact on the theory of computation
- On the probabilistic complexity of finding an approximate solution for linear programming
- Average number of iterations of some polynomial interior-point -- algorithms for linear programming
- On probabilistic algorithm for solving almost all instances of the set partition problem
This page was built for publication: On the average number of steps of the simplex method of linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3040925)
