Computational complexity of Van der Heyden's variable dimension algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's

We show that Van der Heyden's variable dimension algorithm and Dantzig and Cottle's principal pivoting method require 2ⁿ–1 pivot steps to solve a class of linear complementarity problems of ordern. Murty and Fathi have previously shown that the computational effort required to solve a linear complementarity problem of ordern by Lemke's complementary pivot algorithm or by Murty's Bard-type algorithm is not bounded above by a polynomial inn. Our study shows that the variable dimension algorithm and the principal pivoting method have similar worst case computational requirements.