An EP theorem for dual linear complementarity problem

Tibor Illés; Marianna Nagy; Tamas Terlaky

An EP theorem for dual linear complementarity problem

Tibor Illés, Marianna Nagy, Tamas Terlaky

Management Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	3-9
Number of pages	7
Journal	Operations Research Reports
Volume	2007
Issue number	2
Publication status	Published - 1 Feb 2007

Keywords

linear complementarity problem
polynominally solvable problems

Cite this

@article{07947a96c5794f3982c1df9f4cff7f8d,

title = "An EP theorem for dual linear complementarity problem",

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, polynominally solvable problems",

author = "Tibor Ill{\'e}s and Marianna Nagy and Tamas Terlaky",

year = "2007",

month = feb,

day = "1",

language = "English",

volume = "2007",

pages = "3--9",

journal = "Operations Research Reports",

issn = "1215-5918",

number = "2",

}

TY - JOUR

T1 - An EP theorem for dual linear complementarity problem

AU - Illés, Tibor

AU - Nagy, Marianna

AU - Terlaky, Tamas

PY - 2007/2/1

Y1 - 2007/2/1

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

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

KW - linear complementarity problem

KW - polynominally solvable problems

UR - http://www.cs.elte.hu/opres/orr/download/ORR07_2.pdf

M3 - Article

SN - 1215-5918

VL - 2007

SP - 3

EP - 9

JO - Operations Research Reports

JF - Operations Research Reports

IS - 2

ER -

An EP theorem for dual linear complementarity problem

Abstract

Keywords

Other files and links

Fingerprint

Cite this