Some LCPs solvable in strongly polynomial time with Lemke's algorithm

DOI10.1007/s10107-016-0996-4zbMath1356.90145OpenAlexW2332504605MaRDI QIDQ344960

Jong-Shi Pang, Richard W. Cottle, Ilan Adler

Publication date: 25 November 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-016-0996-4

zbMATH Keywords

Lemke's algorithmcovering vectorparametric direction vectorparametric principal pivoting method

Mathematics Subject Classification ID

Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

Linear complementarity model predictive control with limited iterations for box-constrained problems, Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables, Linear-step solvability of some folded concave and singly-parametric sparse optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• CP-rays in simplicial cones
• Strongly polynomial algorithm for a class of combinatorial LCPs
• NP-completeness of the linear complementarity problem
• God and man in the mathematics of Kronecker
• Observations on a class of nasty linear complementarity problems
• On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke's method
• A class of polynomially solvable linear complementarity problems
• Complementary pivot theory of mathematical programming
• On the uniqueness of solutions to linear complementarity problems
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Geometric Properties of Hidden Minkowski Matrices
• Computational complexity of LCPs associated with positive definite symmetric matrices
• Computational complexity of complementary pivot methods
• Bimatrix Equilibrium Points and Mathematical Programming
• The Linear Complementarity Problem