Polynomial interior point algorithms for general linear complementarity problems

Tools

Illes, Tibor and Nagy, Marianna and Terlaky, Tamás (2010) Polynomial interior point algorithms for general linear complementarity problems. Algorithmic Operations Research, 5 (1). pp. 1-12. ISSN 1718-3235

Full text not available in this repository.Request a copy

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 ~κ.

ORCID iDs

Illes, Tibor ORCID logoORCID: https://orcid.org/0000-0002-5396-3148, Nagy, Marianna and Terlaky, Tamás;
CORE (COnnecting REpositories)