An EP theorem for dual linear complementarity problem

Tibor Illés, Marianna Nagy, Tamas Terlaky

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)3-9
Number of pages7
JournalOperations Research Reports
Issue number2
Publication statusPublished - 1 Feb 2007


  • linear complementarity problem
  • polynominally solvable problems


Dive into the research topics of 'An EP theorem for dual linear complementarity problem'. Together they form a unique fingerprint.

Cite this