EP theorem for dual linear complementarity problem

T. Illes, M. Nagy, T. Terlaky

Research output: Contribution to journalArticle

8 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.
LanguageEnglish
Pages233-238
Number of pages5
JournalJournal of Optimization Theory and Applications
Volume140
Issue number2
DOIs
Publication statusPublished - 2009

Fingerprint

Linear Complementarity Problem
Polynomial time
Theorem
Polynomials
Sufficient
Arbitrary
Linear complementarity problem

Keywords

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

Cite this

Illes, T. ; Nagy, M. ; Terlaky, T. / EP theorem for dual linear complementarity problem. In: Journal of Optimization Theory and Applications. 2009 ; Vol. 140, No. 2. pp. 233-238.
@article{b2ec4f25c6d14c9a8c3ed4f4a968f873,
title = "EP theorem for dual linear complementarity problem",
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.",
keywords = "linear complementarity problem, dual LCP, row sufficient matrix, ℘*-matrix, EP theorem",
author = "T. Illes and M. Nagy and T. Terlaky",
year = "2009",
doi = "10.1007/s10957-008-9440-0",
language = "English",
volume = "140",
pages = "233--238",
journal = "Journal of Optimization Theory and Applications",
issn = "0022-3239",
number = "2",

}

EP theorem for dual linear complementarity problem. / Illes, T.; Nagy, M.; Terlaky, T.

In: Journal of Optimization Theory and Applications, Vol. 140, No. 2, 2009, p. 233-238.

Research output: Contribution to journalArticle

TY - JOUR

T1 - EP theorem for dual linear complementarity problem

AU - Illes, T.

AU - Nagy, M.

AU - Terlaky, T.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - linear complementarity problem

KW - dual LCP

KW - row sufficient matrix

KW - ℘-matrix

KW - EP theorem

UR - http://dx.doi.org/10.1007/s10957-008-9440-0

U2 - 10.1007/s10957-008-9440-0

DO - 10.1007/s10957-008-9440-0

M3 - Article

VL - 140

SP - 233

EP - 238

JO - Journal of Optimization Theory and Applications

T2 - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

SN - 0022-3239

IS - 2

ER -