Polynomial interior point algorithms for general linear complementarity problems

Tibor Illes, Marianna Nagy, Tamás Terlaky

Research output: Contribution to journalArticle

Abstract

Linear Complementarity Problems (LCPs) belong 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 coefficient matrix. Following our recently published ideas we generalize affine scaling and predictor-corrector interior point algorithms to solve LCPs with general matrices in EP-sense, namely, our generalized interior point algorithms either solve the problems with rational coefficient matrix in polynomial time or give a polynomial size certificate that our matrix does not belong to the set of P * (~κ) matrices, with arbitrary large, but apriori fixed, rational, positive ~κ.
LanguageEnglish
Pages1-12
Number of pages12
JournalAlgorithmic Operations Research
Volume5
Issue number1
Publication statusPublished - 1 Jan 2010

Fingerprint

Linear complementarity problem
Polynomials
Coefficients
Scaling
NP-complete
Predictors

Keywords

  • linear complementarity problem
  • sufficient matrix
  • interior point method
  • affine scaling method
  • predictor-corrector algorithm

Cite this

Illes, Tibor ; Nagy, Marianna ; Terlaky, Tamás. / Polynomial interior point algorithms for general linear complementarity problems. In: Algorithmic Operations Research. 2010 ; Vol. 5, No. 1. pp. 1-12.
@article{94e08884bf3549b79c60f72e5ca607b2,
title = "Polynomial interior point algorithms for general linear complementarity problems",
abstract = "Linear Complementarity Problems (LCPs) belong 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 coefficient matrix. Following our recently published ideas we generalize affine scaling and predictor-corrector interior point algorithms to solve LCPs with general matrices in EP-sense, namely, our generalized interior point algorithms either solve the problems with rational coefficient matrix in polynomial time or give a polynomial size certificate that our matrix does not belong to the set of P * (~κ) matrices, with arbitrary large, but apriori fixed, rational, positive ~κ.",
keywords = "linear complementarity problem, sufficient matrix, interior point method, affine scaling method, predictor-corrector algorithm",
author = "Tibor Illes and Marianna Nagy and Tam{\'a}s Terlaky",
year = "2010",
month = "1",
day = "1",
language = "English",
volume = "5",
pages = "1--12",
journal = "Algorithmic Operations Research",
issn = "1718-3235",
number = "1",

}

Polynomial interior point algorithms for general linear complementarity problems. / Illes, Tibor; Nagy, Marianna; Terlaky, Tamás.

In: Algorithmic Operations Research, Vol. 5, No. 1, 01.01.2010, p. 1-12.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Polynomial interior point algorithms for general linear complementarity problems

AU - Illes, Tibor

AU - Nagy, Marianna

AU - Terlaky, Tamás

PY - 2010/1/1

Y1 - 2010/1/1

N2 - Linear Complementarity Problems (LCPs) belong 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 coefficient matrix. Following our recently published ideas we generalize affine scaling and predictor-corrector interior point algorithms to solve LCPs with general matrices in EP-sense, namely, our generalized interior point algorithms either solve the problems with rational coefficient matrix in polynomial time or give a polynomial size certificate that our matrix does not belong to the set of P * (~κ) matrices, with arbitrary large, but apriori fixed, rational, positive ~κ.

AB - Linear Complementarity Problems (LCPs) belong 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 coefficient matrix. Following our recently published ideas we generalize affine scaling and predictor-corrector interior point algorithms to solve LCPs with general matrices in EP-sense, namely, our generalized interior point algorithms either solve the problems with rational coefficient matrix in polynomial time or give a polynomial size certificate that our matrix does not belong to the set of P * (~κ) matrices, with arbitrary large, but apriori fixed, rational, positive ~κ.

KW - linear complementarity problem

KW - sufficient matrix

KW - interior point method

KW - affine scaling method

KW - predictor-corrector algorithm

UR - http://journals.hil.unb.ca/index.php/AOR/article/view/11067/0

M3 - Article

VL - 5

SP - 1

EP - 12

JO - Algorithmic Operations Research

T2 - Algorithmic Operations Research

JF - Algorithmic Operations Research

SN - 1718-3235

IS - 1

ER -