EP theorem for dual linear complementarity problem

T. Illes, M. Nagy, T. Terlaky

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

The linear complementarity problem (LCP) belongs to the class of -hard problems. Therefore, we cannot 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)233-238
Number of pages5
JournalJournal of Optimization Theory and Applications
Volume140
Issue number2
DOIs
Publication statusPublished - 2009

Keywords

  • linear complementarity problem
  • dual LCP
  • row sufficient matrix
  • ℘*-matrix
  • EP theorem

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

Cite this