The s-monotone index selection rule for criss-cross algorithms of linear complementarity problems

In this paper we introduce the s-monotone index selection rules for the well-known criss-cross method for solving the linear comple- mentarity problem (LCP). Most LCP solution methods require a priori information about the properties of the input matrix. One of the most general matrix properties often required for finiteness of the pivot algo- rithms (or polynomial complexity of interior point algorithms) is su- ciency. However, there is no known polynomial time method for checking the suciency of a matrix (classification of column suciency of a matrix is co-NP-complete). Following the ideas of Fukuda, Namiki and Tamura, using Existen- tially Polynomial (EP)-type theorems, a simple extension of the criss- cross algorithm is introduced for LCPs with general matrices. Computa- tional results obtained using the extended version of the criss-cross algo- rithm for bi-matrix games and for the Arrow-Debreu market equilibrium problem with dierent market size is presented.