✦ LIBER ✦

Sign-solvable linear complementarity problems

✍ Scribed by Naonori Kakimura

Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 143 KB
Volume: 429
Category: Article
ISSN: 0024-3795
DOI: 10.1016/j.laa.2008.03.022

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals, which can be tested in polynomial time. This characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in O(γ ) time, where γ is the number of the nonzero coefficients.

📜 SIMILAR VOLUMES

A class of linear complementarity proble

A class of linear complementarity problems solvable in polynomial time

✍ Yinyu Ye; Panos M. Pardalos 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 653 KB

Solvability of implicit complementarity

Solvability of implicit complementarity problems

✍ Yeol Je Cho; Jun Li; Nan-jing Huang 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 233 KB

In this paper, we introduce some new notions of (α, γ )-exceptional family of elements (in short, (α, γ )-(EFE)) and (α, β, γ )-exceptional family of elements (in short, (α, β, γ )-(EFE)) for a pair of continuous functions involved in the implicit complementarity problem (in short, ICP). Based upon

Reducing horizontal linear complementari

Reducing horizontal linear complementarity problems

✍ Reha H. Tütüncü; Michael J. Todd 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 609 KB

On degeneracy in linear complementarity

On degeneracy in linear complementarity problems

✍ C.G. Broyden 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 638 KB

On degeneracy in linear complementarity

On degeneracy in linear complementarity problems

✍ G. Saviozzi 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 153 KB

EP theorems and linear complementarity p

EP theorems and linear complementarity problems

✍ Komei Fukuda; Makoto Namiki; Akihisa Tamura 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 809 KB

Let A be a rational n x n square matrix and b be a rational n-vector for some positive integer n. The linear complementarity prnhlem (abbreviated by LCP) is to find a vector (x, y) E R2" satisfying y = Ax + b (x, y) > 0 and the complementarity condition: X! yl = 0 for all i = 1,. , n. The LCP is kn