An EP theorem for DLCP and interior point methods

Tibor Illés, Marianna Nagy, Tamás Terlaky

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

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.
LanguageEnglish
Title of host publicationSOR'07
Subtitle of host publicationThe 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007
EditorsZadnikStirn L, Drobne S
Place of PublicationLjubljana
Pages123-127
Number of pages5
Publication statusPublished - 28 Sep 2007

Fingerprint

Linear complementarity problem
Interior point method
Polynomials
NP-complete

Keywords

  • linear complementarity problem
  • row sufficient matrix
  • EP theorem

Cite this

Illés, T., Nagy, M., & Terlaky, T. (2007). An EP theorem for DLCP and interior point methods. In Z. L, & D. S (Eds.), SOR'07: The 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007 (pp. 123-127). Ljubljana.
Illés, Tibor ; Nagy, Marianna ; Terlaky, Tamás. / An EP theorem for DLCP and interior point methods. SOR'07: The 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007 . editor / ZadnikStirn L ; Drobne S. Ljubljana, 2007. pp. 123-127
@inproceedings{c4c8d67d18894fe7b133b93c37613f02,
title = "An EP theorem for DLCP and interior point methods",
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, EP theorem",
author = "Tibor Ill{\'e}s and Marianna Nagy and Tam{\'a}s Terlaky",
year = "2007",
month = "9",
day = "28",
language = "English",
isbn = "978-961-6165-25-9",
pages = "123--127",
editor = "ZadnikStirn L and Drobne S",
booktitle = "SOR'07",

}

Illés, T, Nagy, M & Terlaky, T 2007, An EP theorem for DLCP and interior point methods. in Z L & D S (eds), SOR'07: The 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007 . Ljubljana, pp. 123-127.

An EP theorem for DLCP and interior point methods. / Illés, Tibor; Nagy, Marianna; Terlaky, Tamás.

SOR'07: The 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007 . ed. / ZadnikStirn L; Drobne S. Ljubljana, 2007. p. 123-127.

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - An EP theorem for DLCP and interior point methods

AU - Illés, Tibor

AU - Nagy, Marianna

AU - Terlaky, Tamás

PY - 2007/9/28

Y1 - 2007/9/28

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 - row sufficient matrix

KW - EP theorem

UR - http://www.optimization-online.org/DB_FILE/2007/03/1603.pdf

UR - http://fgg-web.fgg.uni-lj.si/~/sdrobne/sor/SOR'07%20-%20Proceedings.pdf

M3 - Conference contribution book

SN - 978-961-6165-25-9

SP - 123

EP - 127

BT - SOR'07

A2 - L, ZadnikStirn

A2 - S, Drobne

CY - Ljubljana

ER -

Illés T, Nagy M, Terlaky T. An EP theorem for DLCP and interior point methods. In L Z, S D, editors, SOR'07: The 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007 . Ljubljana. 2007. p. 123-127