Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

DOI10.1007/BF01580646zbMath0613.90094OpenAlexW2014528086MaRDI QIDQ4721880

Michael J. Todd

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580646

zbMATH Keywords

computational complexitysimplex algorithmpivoting algorithmaverage running timelexicographic Lemke algorithmrandom linear complementarity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., Parametric linear programming and anti-cycling pivoting rules, Criss-cross methods: A fresh view on pivot algorithms, Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, A Friendly Smoothed Analysis of the Simplex Method, 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, Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems, Imitation games and computation, Conjugate gradient method for the linear complementarity problem withs-matrix, On design of a survivable network architecture for dynamic routing: Optimal solution strategy and an efficient heuristic, Average number of iterations of some polynomial interior-point -- algorithms for linear programming, A tight analysis of the submodular-supermodular procedure, Pivot rules for linear programming: A survey on recent theoretical developments, Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set, On the complexity of a pivot step of the revised simplex algorithm, Model transform and local parameters. Application to instantaneous attractors

Cites Work

• Unnamed Item
• On the number of vertices of random convex polyhedra
• On the average number of steps of the simplex method of linear programming
• Complementarity in Oriented Matroids
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• A variable dimension algorithm for the linear complementarity problem
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Random polytopes: Their definition, generation and aggregate properties
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• On the expected number of linear complementarity cones intersected by random and semi-random rays
• Bimatrix Equilibrium Points and Mathematical Programming