On the expected number of linear complementarity cones intersected by random and semi-random rays

DOI10.1007/BF01580648zbMath0613.90092MaRDI QIDQ4721878

Nimrod Megiddo

Publication date: 1986

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

zbMATH Keywords

probabilistic analysis of Lemke's algorithmsemi-random ray

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items (4)

Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm ⋮ Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial ⋮ Imitation games and computation ⋮ Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

Cites Work

• Unnamed Item
• On the average number of steps of the simplex method of linear programming
• New results on the average behavior of simplex algorithms
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• The Solution of Systems of Piecewise Linear Equations
• Computational complexity of complementary pivot methods

This page was built for publication: On the expected number of linear complementarity cones intersected by random and semi-random rays