An EP theorem for dual linear complementarity problem

Illés, Tibor and Nagy, Marianna and Terlaky, Tamas (2007) An EP theorem for dual linear complementarity problem. Operations Research Reports, 2007 (2). pp. 3-9. ISSN 1215-5918 (http://www.cs.elte.hu/opres/orr/download/ORR07_2.p...)

Full text not available in this repository.Request a copy

Abstract

The linear complementarity problem (LCP) belongs to the class of NP-complete problems. Therefore we can not expect a polynomial time solution method for LCPs without requiring some special property of the matrix of the problem. We show that the dual LCP can be solved in polynomial time if the matrix is row sufficient, moreover in this case all feasible solutions are complementary. Furthermore we present an existentially polytime (EP) theorem for the dual LCP with arbitrary matrix.

ORCID iDs

Illés, Tibor ORCID logoORCID: https://orcid.org/0000-0002-5396-3148, Nagy, Marianna and Terlaky, Tamas;
CORE (COnnecting REpositories)