The P-Matrix Linear Complementarity Problem -- Generalizations and Specializations

The goal of this thesis is to give a better understanding of the linear complementarity problem with a P-matrix (PLCP). Finding a polynomial time algorithm for the PLCP is a longstanding open problem. Such an algorithm would settle the complexity status of many problems reducing to the PLCP. Most of the papers dealing with the PLCP look at it from an algebraic point of view. We analyze the combinatorial structure of the PLCP. Wherever possible, we state our results for the generalized PLCP (PGLCP), a natural generalization of the PLCP. In the first part of the thesis, we present further generalizations of the PGLCP. We show that the PGLCP fits into the framework of unique sink orientations (USO) of grids. Finding a solution to the PGLCP can therefore be done by finding the sink in a grid USO. Several algorithms are known for this latter task, and we analyze the behavior of some of them on small grids. W