EUVIMEDEUVIMED entdecken
Crossref

The Smallest Computational Complexity for the Linear Complementarity Problem with P-Matrix

LEI LI

Information · 2024

DOI: 10.47880/inf2704-01 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Information, 2024. Verfasst von LEI LI. Die Arbeit nennt 17 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →