## Polynomial Affine-Scaling Algorithms for $P_*(\kappa)$ Linear Complementarity Problems

### T. Illes, C. Roos and T. Terlaky

A family of primal-dual affine-scaling algorithms is presented for Linear Complem
entarity Problems (LCP's) with $P_*$-matrices. These algorithms were first introd uced by
Jansen et al. for solving linear optimization problems and later also applied to LCP's
with semidefinite matrices. We show that the same algorithmic concept applies to LCP's
with $P_*$-matrices and that the resulting algorithms admit polynomial-time iteration
bounds.

Key words: linear complementarity problems, $P_(*)$-matrices, affine-scaling algorithms

Reports of the Faculty of Technical Mathematics and Informatics Nr. 97-21, Delft
University of Technology, Delft, March, 1997

Contact: T.Illes@twi.tudelft.nll