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

DOI10.1007/S10107-016-0996-4zbMATH Open1356.90145OpenAlexW2332504605MaRDI QIDQ344960FDOQ344960

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Complementary pivot theory of mathematical programming
• Computational complexity of LCPs associated with positive definite symmetric matrices
• Bimatrix Equilibrium Points and Mathematical Programming
• The Linear Complementarity Problem
• 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
• NP-completeness of the linear complementarity problem
• God and man in the mathematics of Kronecker
• Observations on a class of nasty linear complementarity problems
• A class of polynomially solvable linear complementarity problems
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Geometric Properties of Hidden Minkowski Matrices
• Computational complexity of complementary pivot methods
• CP-rays in simplicial cones

Cited In (5)

• Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
• Linear complementarity model predictive control with limited iterations for box-constrained problems
• On processability of Lemke's algorithm
• Strongly polynomial algorithm for a class of combinatorial LCPs
• 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)