Linear Complementarity and the Average Volume of Simplicial Cones

Samle [S] has recently shown how to estimate the average number of pivot steps in Lemke’s algorithm for the linear complementarity problem (LCP) in terms of the “volumes” of certain cones. In this paper we discuss the notion of average volumes of cones, and give two applications to the LCP.