The stable b-matching polytope revisited

Abstract The realization of stable b-matchings as matroid kernels yields the existing linear description of the stable b -matching (MM) problem. We revisit that description to derive the dimension, the facets, and the minimum equation system of the stable b -matching polytope. The derived minimal description includes O ( m ) constraints, m being the number of pairs, thus being significantly smaller than the existing one and linear with respect to the problem size. The result carries over to the stable admissions (SA) problem, whose existing linear description relies on an exponential number of comb inequalities; i.e., we identify O ( m ) among these inequalities that define a minimal description of SA.