Linear complementarity problems solvable by a polynomially bounded pivoting algorithm

DOI10.1007/BFB0121072MaRDI QIDQ3707784zbMATH OpenFDO

Authors Jong-Shi Pang, R. Chandrasekaran

Publication date 1985

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

Full work available at URL https://doi.org/10.1007/BFB0121072

zbMATH Keywords

linear complementaritystrictly diagonally dominant matrixP-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)

Recommendations

• Two counterexamples on the polynomial solvability of the linear complementarity problem
• A polynomial-time algorithm for a class of linear complementarity problems
• Pivoting in linear complementarity: Two polynomial-time cases
• A procedure for the one-parametric linear complementarity problem
• An Algorithm for the Linear Complementarity Problem with a P₀ -Matrix

Cited in

(30)

• Principal pivoting method for solving column sufficient complementarity problems
• A procedure for the one-parametric linear complementarity problem
• Two counterexamples on the polynomial solvability of the linear complementarity problem
• A pivoting algorithm for linear programming with linear complementarity constraints
• scientific article; zbMATH DE number 2150958 (Why is no real title available?)
• A class of polynomially solvable linear complementarity problems
• Pivoting in linear complementarity: Two polynomial-time cases
• Counting unique-sink orientations
• A class of linear complementarity problems solvable in polynomial time
• A support submatrix for the generalized linear complementarity problem
• Enumeration of PLCP-orientations of the 4-cube
• A new polynomial time method for a linear complementarity problem
• Good hidden \(P\)-matrix sandwiches
• Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
• Linear complementarity model predictive control with limited iterations for box-constrained problems
• On some properties of \(K\)-type block matrices in the context of complementarity problem
• scientific article; zbMATH DE number 819135 (Why is no real title available?)
• Some LCPs solvable in strongly polynomial time with Lemke's algorithm
• A short proof of finiteness of Murty's principal pivoting algorithm
• A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem
• The Existence of a Short Sequence of Admissible Pivots to an Optimal Basis in LP and LCP
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• CP-rays in simplicial cones
• Extended \(P\)-pairs
• On some classes of matrices related to solving linear complementarity problems as linear programs
• Linear-step solvability of some folded concave and singly-parametric sparse optimization problems
• On the convergence of the block principal pivotal algorithm for the LCP
• An Algorithm for the Linear Complementarity Problem with a P₀ -Matrix
• Generalizations of the hidden Minkowski property

This page was built for publication: Linear complementarity problems solvable by a polynomially bounded pivoting algorithm

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