Polynomial interior point algorithms for general linear complementarity problems

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)