Linear Complementarity Problems ($LCP$s) belong to the class of $\mathbb{NP}$-complete problems. Therefore we can not expect a polynomial time solution method for $LCP$s without requiring some special property of the matrix coefficient matrix. Our aim is to construct some interior point algorithms which, according to the duality theorem in EP form, gives a solution of the original problem or detects the lack of property $\mathcal{P}_*(\tilde\kappa)$ (with arbitrary large, but apriori fixed $\tilde\kappa$) and gives a polynomial size certificate of it in polynomial time (depending on parameter $\tilde{\kappa}$, the initial interior point and the dimension of the $LCP$). We give the general idea of a modification of interior point algorithms and present three concrete methods: affine scaling, long-step path-following and predictor-corrector interior point algorithm.
Citation
unpublished: ORR 2007-3 Eötvös Loránd University of Sciences, Department of Operations Research, Budapest, Hungary 02/2007