Polynomial Interior Point Algorithms for General Linear Complementarity Problems

Authors

  • Tibor Illés Strathclyde University, Glasgow
  • Marianna Nagy Eötvös Loránd University of Science, Budapest
  • Tamás Terlaky Lehigh University, Bethlehem

Keywords:

linear complementarity problem, sufficient matrix, $\mathcal{P}_*$-matrix, interior point method, affine scaling method, predictor-corrector algorithm

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

Author Biographies

Tibor Illés, Strathclyde University, Glasgow

Department of Management Science

Marianna Nagy, Eötvös Loránd University of Science, Budapest

Department of Operation Research

Tamás Terlaky, Lehigh University, Bethlehem

Department of Industrial and Systems Engineering

Downloads

Published

2010-04-14

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

Issue

Section

Articles