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

Vol. 5 No. 1 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.