Answers are grounded in this paper and cite their sources.
The linear complementarity problem LCP(A, q) which consists of finding an real vector z such that Az+q>=0, z>=0, and z^T(Az+q)=0, where A and q are given real matrix and real vector respectively. When A is a P-matrix, LCP(A, q) is a NP-complete problem. Some traditional direct methods for solving the above problem need O(2^n n^2) or O(2^n n^3) number of arithmetic operations at least. This paper proposes a recursive algorithm for solving the LCP(A,q) with A is a P-matrix. The maximum computational complexity for proposed algorithm is not more than 0(2^n) which is the possible smallest computational complexity. And the average computational complexity for proposed algorithm is not more than O((3/2)^n). The proposed algorithm has simple structure and can be implemented easily.
No takes yet. Share an insight, caveat, or question.
Lei Li (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: