Linear Complementarity Problems Solvable by an Efficient Polynomially Bounded Pivoting Algorithm.
Abstract
Applied to two important classes of linear complementarity problems defined by an n x n matrix, the parametric principal pivoting algorithm, using a suitably chosen (and easily computable) parametric vector, terminates with a desired solution after at most n pivot operations. Since each pivot can be performed using at most 0(sq n) arithmetic operations, the total computational complexity of the algorithm for solving these linear complementarity problems is no more than 0(cu m). In one of the two classes of problems being studied, the complexity is 0(sq n ) because the matrix involved is 5-diagonal which allows each pivot to be performed in linear time. Some discussion in connection with Lemke's well-known almost complementary pivoting algorithm is also addressed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1983
- Accession Number
- ADA136405
Entities
People
- J. Pang
Organizations
- University of Wisconsin–Madison