Stability vs. cost of matchings

Abstract

This paper studies the classic minimum-cost perfect matching problem in complete graphs under certain stability constraints. Given some real $\alpha \geq 1$, a matching $M$ is said to be \emph{$\alpha$-stable} if there does not exist any edge $(x, y) \notin M$ such that $\alpha \cdot w(x, y) < \min\{ w(x, x'), w(y, y') \}$, where $x'$ and $y'$ are the vertices matched to $x$ and $y$, respectively, under $M$. Given some real $\beta \geq 1$, the perfect matching $M$ is said to be \emph{$\beta$-minimum} if the total cost of $M$ is at most $\beta$ times larger than that of the minimum-cost perfect matching. We present a simple greedy algorithm that transforms a minimum-cost perfect matching on $2 n$ vertices into an $\alpha$-stable and $\beta$-minimum matching where $\beta = \BigO(n^{\log(1 + 1 / (2 \alpha))})$. In particular, this means that we can obtain a constant approximation for the minimum-cost perfect matching by choosing $\alpha = \BigO(\log n)$. On the negative side, we show that for any $\alpha \geq 1$, there exists a metric graph such that no $\alpha$-stable perfect matching can be $\beta$-minimum unless $\beta = \Omega(n^{\log(1 + 1 / (2 \alpha))})$. Together, our findings establish an asymptotically tight trade-off between the (local) stability and the (global) cost of perfect matchings.