On the complexity of computing the handicap of a sufficient matrix
The class of sufficient matrices is important in the study of the linear complementarity problem(LCP) – some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap. In this paper we show that the handicap of a sufficient matrix may be exponential … Read more