On the average number of steps of the simplex method of linear programming
From MaRDI portal
Publication:3040925
DOI10.1007/BF02591902zbMath0526.90060MaRDI QIDQ3040925
Publication date: 1983
Published in: Mathematical Programming (Search for Journal in Brave)
complexitypath followingsimplex methodaverage number of stepsDantzig's self-dual parametric algorithm
Related Items
Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., Random linear programs with many variables and few constraints, Average polynomial time complexity of some NP-complete problems, Recognizing one-dimensional Euclidean preference profiles, A new family of exponential LP problems, On the efficiency of algorithms of analysis, From Parity and Payoff Games to Linear Programming, A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps, A new simple homotopy algorithm for linear programming. I, Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem, On Estimating Optimal Bases for Linear Programs, Parametric linear programming and anti-cycling pivoting rules, Some remarks on Karmarkar's potential function, On probabilistic algorithm for solving almost all instances of the set partition problem, Invertibility of random fredholm operators, Optimal search algorithm for extrema of a discrete periodic bimodal function, Statistical complexity of the power method for Markov chains, Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, Polyhedral Combinatorics in Combinatorial Optimization, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices, Monotone meshfree methods for linear elliptic equations in non-divergence form via nonlocal relaxation, Recent developments in information-based complexity, A tree traversal algorithm for decision problems in knot theory and 3-manifold topology, Experiments with external pivoting, Halting time is predictable for large models: a universality property and average-case analysis, Exponential lower bounds for finding Brouwer fixed points, A Friendly Smoothed Analysis of the Simplex Method, Probabilistic analysis of a differential equation for linear programming, Asymptotic optimality of a transport-problem plan constructed by the minimum-element method, Simplex-inspired algorithms for solving a class of convex programming problems, Polynomial-time primal simplex algorithms for the minimum cost network flow problem, George Dantzig's impact on the theory of computation, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, On the probabilistic complexity of finding an approximate solution for linear programming, New results on the average behavior of simplex algorithms, Regional complexity analysis of algorithms for nonconvex smooth optimization, Quantitative simulations by matrices, Fast finite methods for a system of linear inequalities, 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, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems, Conditioning of random conic systems under a general family of input distributions, Random inequality constraint systems with few variables, Unnamed Item, Average number of iterations of some polynomial interior-point -- algorithms for linear programming, Estimating the volume of solution space for satisfiability modulo linear real arithmetic, A quadratically convergent method for linear programming, Average case optimality
Cites Work
- A new linear programming algorithm - better or worse than the simplex method?
- Complexity of linear programming
- A convergent process of price adjustment and global Newton methods
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- On the role of the Heisenberg group in harmonic analysis
- The fundamental theorem of algebra and complexity theory
- The Solution of Systems of Piecewise Linear Equations
- The Average number of pivot steps required by the Simplex-Method is polynomial
- Random polytopes: Their definition, generation and aggregate properties
- Computational complexity of complementary pivot methods
- On Algorithms for Solvingf(x)=0
- The Gauss-Bonnet Theorem for Riemannian Polyhedra
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
