STABLE MATCHINGS AND LINEAR INEQUALITIES

The theory of linear inequalities and linear programming was recently applied to study the stable marriage problem which until then has been studied by mostly combinatorial methods. Here we extend the approach to the general stable matching problem in which the structure of match able pairs need not be bipartite. New issues arise in the analysis and we combine linear algebra and graph theory to explore them.