Observations on a class of nasty linear complementarity problems

Earlier papers by Murty 16] and Fathi 7] have exhibited classes of linear complementarity problems for which the computational effort (number of pivot steps) required to solve them by Lemke's algorithm 13] or Murty's algorithm 15] grows exponentially with the pronlem size (number of variables). In this paper we consider the sequences of complementary bases that arise as these problems are solved by the aforementioned algorithms. There is a natural correspondence between these bases and binary n-vectors through which the basis sequences can be identified with particular hamiltonian paths on the unit n-cube and with the binary Gray code representations of the integers from 0 to 2ⁿ-1.