A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems

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 ${\cal O}(1), {\cal O}(\mu),$ and ${\cal 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 ${\cal O} (n^3)$ arithmetic operations. The result implies that interior point methods (IPMs) 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.