Mathematics of Operations Research · 1998 · 160 citations · 17 references
ComputingComputer ScienceMathematicsCombinatoricsComputational GeometryDiscrete MathematicsApproximation AlgorithmsGeometric OptimizationInteger ProgrammingMarriageMatching TheoryConvex Polyhedral TheoryConvex SetsExistence Of Stable MatchingsMarriage ProblemMatching AlgorithmsMatching ProblemsPolyhedral TheoryStable Roommates Problem
We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a 2-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formulation. For the stable marriage problem, we show that a related geometry allows us to express any fractional solution in the stable marriage polytope as a convex combination of stable marriage solutions. This also leads to a genuinely simple proof of the integrality of the stable marriage polytope.
17