Polynomial affine-scaling algorithms for P*(k) linear complementary problems

Tibor Illes, Cornelis Roos, Tamás Terlaky

Research output: Chapter in Book/Report/Conference proceedingConference contribution book


A family of primal-dual affine-scaling algorithms is presented for Linear Complementarity Problems (LCP's) with P*-matrices. These algorithms were first introduced by Jansen et al. for solving linear optimization problems and later also applied to LCP's with positive 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.
Original languageEnglish
Title of host publicationRecent Advances in Optimization
Subtitle of host publicationProceedings of the 8th French-German Conference on Optimization Trier, July 21–26, 1996
Number of pages19
Publication statusPublished - 1997
Externally publishedYes

Publication series

NameLecture Notes in Economics and Mathematical Systems
PublisherSpringer Berlin Heidelberg
ISSN (Print)0075-8442


  • linear complementary problems
  • matrices
  • affine scaling method
  • affine-scaling algorithms


Dive into the research topics of 'Polynomial affine-scaling algorithms for P*(k) linear complementary problems'. Together they form a unique fingerprint.

Cite this