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

DOI10.1007/S10107-016-0996-4MaRDI QIDQ344960zbMATH OpenOpenAlexFDO

Authors Ilan Adler, R. W. Cottle, Jong-Shi Pang

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)

Recommendations

• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Polynomial interior point algorithms for general linear complementarity problems
• A polynomial-time algorithm for a class of linear complementarity problems
• Strongly polynomial algorithm for a class of combinatorial LCPs
• scientific article; zbMATH DE number 653034

Cites work

• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• A class of polynomially solvable linear complementarity problems
• Bimatrix Equilibrium Points and Mathematical Programming
• CP-rays in simplicial cones
• Complementary pivot theory of mathematical programming
• Computational complexity of LCPs associated with positive definite symmetric matrices
• Computational complexity of complementary pivot methods
• Geometric Properties of Hidden Minkowski Matrices
• God and man in the mathematics of Kronecker
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• NP-completeness of the linear complementarity problem
• 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
• On the uniqueness of solutions to linear complementarity problems
• Strongly polynomial algorithm for a class of combinatorial LCPs
• The Linear Complementarity Problem

Cited in

(5)

• Linear complementarity model predictive control with limited iterations for box-constrained problems
• Strongly polynomial algorithm for a class of combinatorial LCPs
• On processability of Lemke's algorithm
• Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
• Linear-step solvability of some folded concave and singly-parametric sparse optimization problems

This page was built for publication: Some LCPs solvable in strongly polynomial time with Lemke's algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344960)