Linear complementarity problems solvable by a polynomially bounded pivoting algorithm

DOI10.1007/BFb0121072zbMath0582.90099MaRDI QIDQ3707784

R. Chandrasekaran, Jong-Shi Pang

Publication date: 1985

Published in: Mathematical Programming Essays in Honor of George B. Dantzig Part II (Search for Journal in Brave)

zbMATH Keywords

linear complementarityP-matrixstrictly diagonally dominant matrixparametric principal pivotinghidden Z transposepolynomial testing procedure

Mathematics Subject Classification ID

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

Related Items

On some classes of matrices related to solving linear complementarity problems as linear programs ⋮ Extended \(P\)-pairs ⋮ Some LCPs solvable in strongly polynomial time with Lemke's algorithm ⋮ Linear complementarity model predictive control with limited iterations for box-constrained problems ⋮ A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem ⋮ Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables ⋮ Linear-step solvability of some folded concave and singly-parametric sparse optimization problems ⋮ Counting unique-sink orientations ⋮ A class of linear complementarity problems solvable in polynomial time ⋮ Two counterexamples on the polynomial solvability of the linear complementarity problem ⋮ Enumeration of PLCP-orientations of the 4-cube ⋮ Generalizations of the hidden Minkowski property ⋮ A class of polynomially solvable linear complementarity problems ⋮ Good hidden \(P\)-matrix sandwiches ⋮ On the convergence of the block principal pivotal algorithm for the LCP ⋮ CP-rays in simplicial cones