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

hidden Z transposelinear complementarityP-matrixparametric principal pivotingpolynomial testing procedurestrictly diagonally dominant matrix

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

(31)

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

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)