An EP theorem for DLCP and interior point methods

Illés, Tibor and Nagy, Marianna and Terlaky, Tamás; L, ZadnikStirn and S, Drobne, eds. (2007) An EP theorem for DLCP and interior point methods. In: SOR'07. Slovenian Society of Informatics, Ljubljana, pp. 123-127. ISBN 978-961-6165-25-9

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: https://orcid.org/0000-0002-5396-3148

• Share and Export
  

  RDF+XMLBibTeXRIOXX2 XMLRDF+N-TriplesJSONDublin CoreAtomSimple MetadataReferMETSHTML CitationASCII CitationOpenURL ContextObjectEndNoteOpenURL ContextObject in SpanMODSMPEG-21 DIDLEP3 XMLData Cite XMLRIS (EndNote Online, Zotero, Ref manager, etc)RDF+N3Multiline CSV
• Item metadata

  Item type:	Book Section
  ID code:	58710
  Dates:	Date Event 28 September 2007 Published
  Keywords:	linear complementarity problem, row sufficient matrix, EP theorem, Management. Industrial Management, Management Science and Operations Research
  Subjects:	Social Sciences > Industries. Land use. Labor > Management. Industrial Management
  Department:	Strathclyde Business School > Management Science
  Depositing user:	Pure Administrator
  Date deposited:	16 Nov 2016 14:26
  Last modified:	18 Jan 2023 12:28
  Related URLs:	Related item Event
  URI:	https://strathprints.strath.ac.uk/id/eprint/58710