Computational complexity of Van der Heyden's variable dimension algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's

DOI10.1007/BF02591869zbMath0512.90093OpenAlexW2067610090MaRDI QIDQ3657800

Akli Gana, John R. Birge

Publication date: 1983

Published in: Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitylinear complementarity problemvariable dimension algorithmpivot step requirement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

A polynomial-time algorithm for a class of linear complementarity problems, Conjugate gradient method for the linear complementarity problem withs-matrix, Linear, quadratic, and bilinear programming approaches to the linear complementarity problem

Uses Software

• PLALGO

Cites Work

• Unnamed Item
• Complementary pivot theory of mathematical programming
• Computational complexity of LCPs associated with positive definite symmetric matrices
• A variable dimension algorithm for the linear complementarity problem
• Completely- matrices
• Computational complexity of complementary pivot methods
• On the computational complexity of piecewise-linear homotopy algorithms
• Bimatrix Equilibrium Points and Mathematical Programming