The Smallest Computational Complexity for the Linear Complementarity Problem with P-Matrix
Information · 2024
DOI: 10.47880/inf2704-01 ↗Kurz gefasst
Fachartikel in der Zeitschrift Information, 2024. Verfasst von LEI LI. Die Arbeit nennt 17 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
LI, L. (2024). The Smallest Computational Complexity for the Linear Complementarity Problem with P-Matrix. Information. https://doi.org/10.47880/inf2704-01
Vancouver
LI L. The Smallest Computational Complexity for the Linear Complementarity Problem with P-Matrix. Information. 2024. doi:10.47880/inf2704-01
BibTeX
@article{LI2024,
author = {LI, LEI},
title = {The Smallest Computational Complexity for the Linear Complementarity Problem with P-Matrix},
journal = {Information},
year = {2024},
doi = {10.47880/inf2704-01}
}
EUVIMED