Optimization Online


An EP theorem for dual linear complementarity problem

Illés Tibor (illes***at***math.elte.hu)
Marianna Nagy (nmariann***at***cs.elte.hu)
Tamás Terlaky (terlaky***at***mcmaster.hu)

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.

Keywords: Linear complementarity problem, row sufficient matrix, P*-matrix, EP theorem

Category 1: Linear, Cone and Semidefinite Programming (Other )

Citation: unpublished: Operation Research Reports, ORR 2007-2 Eötvös Loránd University of Sciences, Department of Operations Research, Budapest, Hungary, 2007/02

Download: [PDF]

Entry Submitted: 03/02/2007
Entry Accepted: 03/02/2007
Entry Last Modified: 01/20/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society