Vol. 5 No. 1 (2010)

Polynomial Interior Point Algorithms for General Linear Complementarity Problems

Tibor Illés
Strathclyde University, Glasgow
Marianna Nagy
Eötvös Loránd University of Science, Budapest
Tamás Terlaky
Lehigh University, Bethlehem
Published April 14, 2010
  • linear complementarity problem,
  • sufficient matrix,
  • $\mathcal{P}_*$-matrix,
  • interior point method,
  • affine scaling method,
  • predictor-corrector algorithm
  • ...More
How to Cite
Illés, T., Nagy, M., & Terlaky, T. (2010). Polynomial Interior Point Algorithms for General Linear Complementarity Problems. Algorithmic Operations Research, 5(1), Pages 1 - 12. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/11067


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