Illés, Tibor; Peng, Jiming; Roos, Cornelis; Terlaky, Tamás A strongly polynomial rounding procedure yielding a maximally complementary solution for \(P_*(\kappa)\) linear complementarity problems. (English) Zbl 1010.90082 SIAM J. Optim. 11, No. 2, 320-340 (2000). Summary: We deal with Linear Complementarity Problems (LCPs) with \(P_*(\kappa)\) matrices. First we establish the convergence rate of the complementary variables along the central path. The central path is parameterized by the barrier parameter \(\mu\), as usual. Our elementary proof reproduces the known result that the variables on or close to the central path fall apart in three classes in which these variables are \({\mathcal O}(1), {\mathcal O}(\mu),\) and \({\mathcal O}(\sqrt{\mu})\), respectively. The constants hidden in these bounds are expressed in or bounded by the input data. All this is preparation for our main result: a strongly polynomial rounding procedure. Given a point with sufficiently small complementarity gap and which is close enough to the central path, the rounding procedure produces a maximally complementary solution in at most \({\mathcal O}(n^3)\) arithmetic operations.The result implies that interior point methods not only converge to a complementary solution of \(P_*(\kappa)\) LCPs, but, when furnished with our rounding procedure, they can also produce a maximally complementary (exact) solution in polynomial time. Cited in 21 Documents MSC: 90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) 90C51 Interior-point methods Keywords:linear complementarity problems; \(P_*(\kappa)\) matrices; error bounds on the size of the variables; optimal partition; maximally complementary solution; rounding procedure PDFBibTeX XMLCite \textit{T. Illés} et al., SIAM J. Optim. 11, No. 2, 320--340 (2000; Zbl 1010.90082) Full Text: DOI